题目描述:
Description:
Count the number of prime numbers less than a non-negative number, n.
解法一：
遍历从1-n的所有整数，查看是否为质数，是质数借助一个则将该整数存入一个容器中，判断一个数是否为质数，可以遍历在容器中且小于n的平方根的质数，如果n可以被符合条件的质数整除，则这个数不是质数。代码如下：
class Solution {
public:
vector<int> prime_vec;
bool isPrime(int n)
{
if (n<)
return false;
else if (n == )
return true;
else if (n % == )
return false;
else
{
int n_sqr = sqrt(n);
for (int i = ; prime_vec[i] <= n_sqr; i ++) {
if(n % prime_vec[i] == )
return false;
}
return true;
}
}
int countPrimes(int n) {
int counter = ;
for (int i = ; i < n; i ++) {
if (isPrime(i)) {
prime_vec.push_back(i);
counter ++;
}
}
for (auto i = prime_vec.begin(); i != prime_vec.end(); i ++) {
cout << *i << endl;
}
return counter;
}
};
解法二：
上述代码的执行效率不高，看了其他人的解题思路之后，豁然开朗，*上有一个动态演示的效果图，算法思想名叫“晒数法”，连接如下：
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
看了这个效果图我马上进行了自己的实现，代码如下：
class Solution {
public:
int countPrimes(int n) {
int counter = ;
if (n < )
return counter;
int upper = sqrt(n);
vector<bool> flag_vec(n, false);
int i = ;
while (i < n) {
cout << i << endl;
counter ++;
if(i <= upper)
{
for (long long j = i * i; j < n; j += i)
flag_vec[j] = true;
}
++ i;
while (flag_vec[i] == true)
++ i;
}
return counter;
}
};
可以很清楚地知道，解法二比解法一要好很多，因为在从小到大遍历的过程中，所有的数仅遍历一遍，这解法一虽然比暴力的O（n*n）的方法好一些，但是时间复杂度还是大于O（n）的，而晒数法的时间复杂度仅为O（n）。