D57 762. Prime Number of Set Bits in Binary Representation

题目链接

762. Prime Number of Set Bits in Binary Representation

题目分析

对给定范围内的每个整数，返回其二进制形式下，数字 1 出现的次数为质数的次数。

例如 11111，1 出现了 5 次，5 是质数。
再如 10111，1 出现了 4 次，4 不是质数。

思路

由于题目固定了范围为 1~10^6，10^6 次方为 1 千万。小于 2^24。即最多只会出现 24 次 1。

由于小于 24 的质数个数有限，我们直接写死 24 以内的质数。

对每一个数字，计算 1 出现的次数。再判断出现次数是否在这个质数数组内。

存在则符合题目要求的数字，否则不计入该数字。

最终代码

<?php
class Solution {

    /**
     * @param Integer $L
     * @param Integer $R
     * @return Integer
     */
    function countPrimeSetBits($L, $R) {$primes = [2,3,5,7,11,13,17,19,23];
        $nums = range($L,$R);
        $primeOnes = 0;
        foreach($nums as $num){$ones = array_filter(str_split(decbin($num)), function($val){return $val == '1';});
            if(in_array(count($ones),$primes)){$primeOnes++;}
        }
        
        return $primeOnes;
    }
}

若觉得本文章对你有用，欢迎用爱发电资助。