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出现的次数。再判断出现次数是否在这个质数数组内。

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

最终代码

<?phpclass 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;    }}

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