LeetCode: 204. Count Primes
题目描述
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.
解题思路
首先统计素数表,然后统计素数 表中的内容。
AC 代码
class Solution
{
public:
int countPrimes(int n)
{
vector<bool> isPrime(n, true);
isPrime[0] = false;
isPrime[1] = false;
isPrime[2] = true;
// 标记非素数
for(int i = 2; i < n; ++i)
{
if(isPrime[i] == false) continue;
int notPrime = i*2;
while(notPrime < n)
{
isPrime[notPrime] = false;
notPrime += i;
}
}
// 统计素数的数量
int cnt = 0;
for(int i = 0; i < n; ++i)
{
cnt += isPrime[i];
}
return cnt;
}
};