题目描述

给定两个整数L和R，统计出区间[L, R]中满足如下条件的数的个数：

• 二进制表示里1的个数是质数；

注意:

• L, R满足 L <= R，且均在区间[1, 10^6]中；
• R - L不大于10000；

样例1

输入：L = 6, R = 10
输出：4
解释：
6 -> 110 (包含2个1, 2是质数)
7 -> 111 (包含3个1, 3是质数)
9 -> 1001 (包含2个1, 2是质数)
10->1010 (包含2个1, 2是质数)

样例2

输入：L = 10, R = 15
输出：5
解释：
10 -> 1010 (包含2个1, 2是质数)
11 -> 1011 (包含3个1, 3是质数)
12 -> 1100 (包含2个1, 2是质数)
13 -> 1101 (包含3个1, 3是质数)
14 -> 1110 (包含3个1, 3是质数)
15 -> 1111 (包含4个1, 4不是质数)

算法

(枚举，位运算) $O(n)$

由于区间[L, R]中最多只有10000个数，所以我们可以直接枚举区间中的每个数，然后统计出二进制表示中1个数s，再判断s是否是质数即可。

由于L, R均不大于1000000，所以其二进制表示最多有20位，我们可以预先将20以内的所有质数都存到哈希表中，然后就可以 $O(1)$ 判断s是否是质数了。

另外这里有个常用技巧：

判断整数x的第k位是否是1，可以使用位运算来做：x >> k & 1。

时间复杂度分析：总共需要枚举 $n$ 个数，每个数最多枚举20位二进制位，所以总计算量是 $20n$，时间复杂度是 $O(n)$。

C++ 代码

class Solution {
public:
    int countPrimeSetBits(int L, int R) {
        unordered_set<int> primes{2, 3, 5, 7, 11, 13, 17, 19};
        int res = 0;
        for (int i = L; i <= R; i ++ ) {
            int s = 0;
            for (int j = i; j; j >>= 1) s += j & 1;
            res += primes.count(s);
        }
        return res;
    }
};