204. Count Primes M ！！

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)

这个仅仅beat 了40% 的

class Solution {
public:
    int countPrimes(int n) {
        vector<bool> M(n,true); // M[i] means, if value i is prime number
        int 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:

Runtime error: load of value 127, which is not a valid value for type 'bool'

See this page: https://stackoverflow.com/questions/1920430/c-array-initialization