Count Primes – LeetCode 204
Problem
Description
Count the number of prime numbers less than a non-negative number, n.
Answer
Original
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int countPrimes(int n) {
if (n<=2) return 0;
vector<bool> passed(n, false);
int sum = 1;
int upper = sqrt(n);
for (int i=3; i<n; i+=2) {
if (!passed[i]) {
sum++;
if (i>upper) continue;
for (int j=i*i; j<n; j+=i) {
passed[j] = true;
}
}
}
return sum;
}
};
|
思路
标准的数学解，用的是小学就会的数筛法，正式称为埃拉托斯特尼筛法。时间复杂度$O(n)$，空间复杂度$O(n)$。
耗时$19$ ms，排名$12.25\%$
Better
思路
还没看到更好的思路。