难度:Easy Count the number of prime numbers less than a non-negative number, n.
Example:Input: 10Output: 4Explanation: 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%的用户
另有一种方法,叫厄拉多塞筛法,可以更有效地找出质数。