暴力法(超时)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
int countPrimes(int n) {
if(n <= 2)
return 0;
int ret = 1;
for(int i = 3; i < n; ++i)
{
ret += isPrime(i);
}
return ret;
}
private:
int isPrime(int x)
{
for(int i = 2; i * i <= x; ++i)
{
if(x % i == 0)
return 0;
}
return 1;
}
};
|
埃氏筛
计数质数 - 计数质数 - 力扣（LeetCode） (leetcode-cn.com)
如果 xx 是质数，那么大于 xx 的 xx 的倍数 2x,3x,2x,3x,… 一定不是质数，因此我们可以从这里入手。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int countPrimes(int n) {
vector<int> memo(n, 1);
int ret = 0;
for(int i = 2; i < n; ++i)
{
if(memo[i])
{
++ret;
for(long j = long(i) * i; j < n; j += i)
{
memo[j] = 0;
}
}
}
return ret;
}
};
|
线性筛
保留