problem
762. Prime Number of Set Bits in Binary Representation
solution1:
class Solution {
public:
int countPrimeSetBits(int L, int R) {
int res = 0;
int bits = 0;
for(int i=L; i<=R; i++)
{
bits = countBits(i);
if(isPrime(bits) && bits!=1 ) res++;//err...
}
return res;
}
int countBits(int num)
{
int res = 0;
while(num>0)
{
if(num & 1 == 1) res++;
num >>= 1;
}
return res;
}
bool isPrime(int num)
{
for(int i=sqrt(num); i>1; i--)
{
if(num%i==0) return false;
}
return true;
}
};
solution2:题目中给了数的大小范围 R <= 106 < 220，那么统计出来的非零位个数cnt只需要检测是否是20以内的质数即可，所以将20以内的质数都放入一个HashSet中，然后统计出来cnt后，直接在HashSet中查找有没有即可。
class Solution {
public:
int countPrimeSetBits(int L, int R) {
int res = 0;
unordered_set<int> primes{2, 3, 5, 7, 11, 13, 17, 19};
for(int i=L; i<=R; i++)
{
int bits = 0;
int tmp = i;
while(tmp){
if(tmp&1 == 1) bits++;
tmp >>= 1;
}
res += primes.count(bits);
}
return res;
}
};
参考
1. Leetcode_easy_762. Prime Number of Set Bits in Binary Representation;
2. Grandyang;
完