204.Count Primes
204.Count Primes
难度:Easy Count the number of prime numbers less than a non-negative number, n.
1
Example:
2
3
Input: 10
4
Output: 4
5
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
Copied!
统计质数数目可以使用一个数组存储,但是判断质数,可以使用已经存在的质数来判断。如果不是质数,一定可以因式分解成质数,不比一个一个判断,减少判断次数。
1
class Solution {
2
vector<int> prime ={2,3,5,7,11};
3
bool isPrime(int n)
4
{
5
// for( int k=2;k<=sqrt(n);k++)
6
for(int k=0;k<prime.size();k++)
7
{
8
if(prime[k] > sqrt(n)) break;
9
if(n%prime[k] ==0) return false;
10
11
}
12
return true;
13
}
14
public:
15
int countPrimes(int n) {
16
if(n<=prime[prime.size()-1])
17
for(int i=0;i<prime.size();i++)
18
if(n<=prime[i]) return i;
19
for(int k = prime[prime.size()-1]+2 ; k<n; k+=2)
20
{
21
if( isPrime(k)) prime.push_back(k);
22
}
23
// for(auto i: prime)
24
// cout<<i<<" ";
25
return prime.size();
26
27
}
28
};
Copied!
执行用时 :360 ms, 在所有 C++ 提交中击败了21.11%的用户 内存消耗 :10.9 MB, 在所有 C++ 提交中击败了40.63%的用户
另有一种方法,叫厄拉多塞筛法,可以更有效地找出质数。
Copy link