考点
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
private:
unordered_set<int> primeArr = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
int bitCount(int n) {
n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f);
n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff);
n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff);
return n;
}
public:
int countPrimeSetBits(int left, int right) {
int ans = 0;
for (int i = left; i <= right; i++) {
if (primeArr.count(bitCount(i))) ans++;
}
return ans;
}
};
|
时间复杂度：\(O\left( \left( right-left
\right) \cdot \log right \right)\)
空间复杂度：\(O\left( C
\right)\)，\(C\)等于质数打表数组的长度
思路
若使用常规判断质数代码，时间复杂度就高达\(O\left( \sqrt{right} \right)\)
1
2
3
4
5
6
7
8
9
| bool primeJudge(int num) {
if (num < 2) return false;
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
|
一个int类型的整数，其比特位数肯定不超过32；所以直接用哈希表，将32以内的质数打表保存即可，这样时间复杂度可降为常数
这里判断整数的1个数使用的是191. 位1的个数提到的分治法，不再赘述