204.Count Primes

204.Count Primes

难度:Easy Count the number of prime numbers less than a non-negative number, n.

Example:

Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

统计质数数目可以使用一个数组存储，但是判断质数，可以使用已经存在的质数来判断。如果不是质数，一定可以因式分解成质数，不比一个一个判断，减少判断次数。

class Solution {
vector<int> prime ={2,3,5,7,11};
bool isPrime(int n)
{
    // for( int k=2;k<=sqrt(n);k++)
    for(int k=0;k<prime.size();k++)
    {
        if(prime[k] > sqrt(n)) break;
        if(n%prime[k] ==0) return false;
        
    }
    return true;
}
public:
    int countPrimes(int n) {
        if(n<=prime[prime.size()-1])
        for(int i=0;i<prime.size();i++)
            if(n<=prime[i]) return i;
        for(int k = prime[prime.size()-1]+2 ; k<n; k+=2)
        {
            if( isPrime(k)) prime.push_back(k);
        }
        // for(auto i: prime)
        // cout<<i<<" ";
        return prime.size();
        
    }
};

执行用时 :360 ms, 在所有 C++ 提交中击败了21.11%的用户 内存消耗 :10.9 MB, 在所有 C++ 提交中击败了40.63%的用户

另有一种方法，叫厄拉多塞筛法，可以更有效地找出质数。