[思路]：寻找给定两个整数区间内的整数的二进制表示拥有素数个数的1；
例如：
21的二进制：10101 ，三位1，为素数；
1 不是素数；
-
一种方法是：计算整数的二进制表示；然后统计1的个数；
-
另一种方法： 使用位运算，通过移位和1相与，来统计1的个数；
本次题限制【1,100000】之间，最大位数20位，所有位数的素数有：
{2, 3, 5, 7, 11, 13, 17, 19}
int countPrimeSetBits(int L, int R) {
set<int> primes = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 };
int cnt = 0;
for (int i = L; i <= R; i++) {
int bits = 0;
for (int n = i; n>0; n >>= 1)
bits += n & 1;
cnt += primes.count(bits);
}
return cnt;
}
网友评论