这么一道求素数个数的简单题目，首先尝试最简单的暴力破解法：
class Solution {
public:
int countPrimes(int n) {
int cnt = 0;
for(int i = 2;i < n;i++)
{
if(isPrime(i))
cnt++;
}
return cnt;
}
private:
bool isPrime(int n) {
for(int i = 2;i <= n/2;i++)
{
if(n % i == 0)
return false;
}
return true;
}
};执行结果也和预期一致：
17 / 20 test cases passed.
Status: Time Limit Exceeded
Submitted: 0 minutes ago
/*
algorithm Sieve of Eratosthenes is
input: an integer n > 1.
output: all prime numbers from 2 through n.
let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.
for i = 2, 3, 4, ..., not exceeding √n do
if A[i] is true
for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n do
A[j] := false
return all i such that A[i] is true.
*/
class Solution {
public:
int countPrimes(int n) {
if(n <= 2) return 0;
int cnt = n - 2;
vector<bool> prime(n,true);
prime[0] = prime[1] = false;
for(int i = 2;i < sqrt(n);i++)
{
if(prime[i])
{
for(int j = i * i;j < n;j += i)
{
prime[j] = false;
}
}
}
return count(prime.begin(),prime.end(),true);
}
};运行时间：
Runtime: 180 ms, faster than 42.90% of C++ online submissions for Count Primes.
Memory Usage: 6.5 MB, less than 7.72% of C++ online submissions for Count Primes.这里我自作聪明的想不调用count，本以为速度会快，但实际上再一个二层循环最内层增加语句效率反而更差：
/*
algorithm Sieve of Eratosthenes is
input: an integer n > 1.
output: all prime numbers from 2 through n.
let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.
for i = 2, 3, 4, ..., not exceeding √n do
if A[i] is true
for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n do
A[j] := false
return all i such that A[i] is true.
*/
class Solution {
public:
int countPrimes(int n) {
if(n <= 2) return 0;
int cnt = n - 2;
vector<bool> prime(n,true);
prime[0] = prime[1] = false;
for(int i = 2;i < sqrt(n);i++)
{
if(prime[i])
{
for(int j = i * i;j < n;j += i)
{
if(prime[j])
cnt--;
prime[j] = false;
}
}
}
return cnt;
}
};运行时间：
20 / 20 test cases passed.
Status: Accepted
Runtime: 232 ms
Memory Usage: 6.7 MB
另外这里如果不判断n的大小，会运行出错原因是vector