28
04/2015
[LeetCode] Count Primes
Count Primes
Description:
Count the number of prime numbers less than a non-negative number, n
解题思路：
题意为求小于n的质数的个数。有两种方法：
1、naive办法，对小于n的每个数，检查是否为质数。而检查m是否为质数，需要验证是否都不能被2~pow(m, 0.5)整除。这个方法的时间复杂度为O(n^2)，空间复杂度为O(1)。会产生超时错误。
class Solution {
public:
int countPrimes(int n) {
int count=0;
for(int i=0; i<n; i++){
if(isPrim(n)){
count++;
}
}
return count;
}
bool isPrim(int n){
if(n<=1){
return false;
}
double up=pow(n, 0.5);
for(int i=2; i<=up; i++){
if(n%i==0){
return false;
}
}
return true;
}
};2、用一个数组来标记是否为质数。大体思想是：2是质数，那么2的所有倍数（除本身）都不是质数，此时标记2的所有倍数（除本身）为非质数。从小到大扫描，若当前扫描的是质数，则标记其所有的非本身的倍数为非质数。最后对所有质数计数即可。下面为代码：
class Solution {
public:
int countPrimes(int n) {
if(n<2){
return 0;
}
bool primFlag[n];
memset(primFlag, 1, sizeof(bool) * n);
primFlag[0]=primFlag[1]=false;
double up = pow(n, 0.5);
for(int i=2; i<up; i++){
if(primFlag[i]){
for(int j=2; j*i<n; j++){
primFlag[j*i]=false;
}
}
}
int count=0;
for(int i=0; i<n; i++){
if(primFlag[i]){
count++;
}
}
return count;
}
};这个算法的空间复杂度为fO(n)，时间复杂度比较复杂。该方法称为Eratosthenes算法。
3、算法2的改进：
class Solution {
public:
int countPrimes(int n) {
if(n<2){
return 0;
}
bool primFlag[n];
memset(primFlag, 1, sizeof(bool) * n);
primFlag[0]=primFlag[1]=false;
double up = pow(n, 0.5);
int count=n-2;
for(int i=2; i<up; i++){
if(primFlag[i]){
for(int j=2; j*i<n; j++){
if(primFlag[j*i]){
primFlag[j*i]=false;
count--;
}
}
}
}
return count;
}
};转载请注明：康瑞部落 » [LeetCode] Count Primes
0 条评论