Q:
Given an integer n, return the number of prime numbers that are strictly less than n.
Example 1:
Input: n = 10 Output: 4 Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
Example 2:
Input: n = 0 Output: 0
Example 3:
Input: n = 1 Output: 0
Constraints:
0 <= n <= 5 * 106
A:
挨个过滤，看是否能被已经发现的prime Number整除。 LTE
class Solution {
public:
int countPrimes(int n) {
if(n<=2)
return 0;
int res = 0;
vector<int> P{2};
for(int i = 3;i<n;++i){
bool found = false;
for(const auto & val : P){
if(i % val ==0){
found = true;
break;
}
}
if(! found){
P.push_back(i);
}
}
return P.size();
}
};
*****************用筛法*********************
- Time complexity: O(n log log n)
class Solution {public:int countPrimes(int n) {vector<bool> M(n,true); // M[i] means, if value i is prime numberint count = 0;for(int i =2;i<n;i++){if(M[i]){++count;int nextCount = i+i;while(nextCount<n){M[nextCount] = false;nextCount += i;}}}return count;}};
进一步的更改是， 在内层的循环里 不从2*i 开始， 而是从 i * i 开始， 好好想想，这是为什么呢？ beat 95%
class Solution {
public:
int countPrimes(int n) {
if(n<3)
return 0;
vector<int> M(n, 1); // M[i] means, if value i is prime number
for(int i =2; i*i < n;i++){
if(M[i]){
for(int j = i*i; j<n ; j+=i)
M[j] = 0;
}
}
return std::accumulate(M.begin(), M.end(), 0) -2;
}
};
Mistakes:
最新的，需要考虑 n <=0 的情况。 艹。 之前没有的
bool A[n+1]; // n is not included 有些时候，C++不会将其设为默认值。i.e. 会有error:
