文章作者：Tyan
博客：noahsnail.com | CSDN | 简书
1. Description
2. Solution
Version 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31class Solution {
public:
int countPrimes(int n) {
if(n < 3) {
return 0;
}
int count = 1;
for(int i = 3; i < n; i += 2) {
if(isPrime(i)) {
count++;
}
}
return count;
}
private:
bool isPrime(int n) {
if(n < 2) {
return false;
}
if(n == 2 || n == 3) {
return true;
}
for(int i = 2; i * i <= n; i++) {
if(n % i == 0) {
return false;
}
}
return true;
}
};Version 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24class Solution {
public:
int countPrimes(int n) {
if(n <= 2) {
return 0;
}
bool flag[n];
int count = 1;
memset(flag, true, sizeof(flag));
for(int i = 2; i * i < n; i++) {
if(flag[i]) {
for(int j = i * i; j < n; j += i) {
flag[j] = false;
}
}
}
for(int i = 3; i < n; i += 2) {
if(flag[i]) {
count++;
}
}
return count;
}
};
