给定两个整数 L 和 R ，找到闭区间 [L, R] 范围内，计算置位位数为质数的整数个数。
（注意，计算置位代表二进制表示中1的个数。例如 21 的二进制表示 10101 有 3 个计算置位。还有，1 不是质数。）
示例 1:
输入: L = 6, R = 10 输出: 4 解释: 6 -> 110 (2 个计算置位，2 是质数) 7 -> 111 (3 个计算置位，3 是质数) 9 -> 1001 (2 个计算置位，2 是质数) 10-> 1010 (2 个计算置位，2 是质数)
示例 2:
输入: L = 10, R = 15 输出: 5 解释: 10 -> 1010 (2 个计算置位, 2 是质数) 11 -> 1011 (3 个计算置位, 3 是质数) 12 -> 1100 (2 个计算置位, 2 是质数) 13 -> 1101 (3 个计算置位, 3 是质数) 14 -> 1110 (3 个计算置位, 3 是质数) 15 -> 1111 (4 个计算置位, 4 不是质数)
注意:
- L, R 是 L <= R 且在 [1, 10^6] 中的整数。
- R - L 的最大值为 10000。
class Solution {
public:
int countPrimeSetBits(int L, int R)
{
vector<int> prim = GetPrim();
int len = prim.size();
map<int ,int> check;
for(int i = 0; i < len; i++)
{
check[prim[i]] = 1;
}
int res = 0;
for(int i = L; i <= R; i++)
{
int temp = i;
int x = 0;
while(temp)
{
if(temp & 1 == 1)
x++;
temp >>= 1;
}
if(check[x] == 1)
res++;
}
return res;
}
vector<int> GetPrim()
{
int len = 64;
vector<int> check(65, 0);
vector<int> res;
check[0] = 1;
check[1] = 1;
for(int i = 2; i <= 64; i++)
{
if(check[i] == 1)
continue;
for(int j = i + i; j <= 64; j += i)
{
check[j] = 1;
}
}
for(int i = 1; i <= 64; i++)
{
if(check[i] != 1)
res.push_back(i);
}
return res;
}
};