难度: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%的用户
另有一种方法，叫厄拉多塞筛法，可以更有效地找出质数。