首页 > 代码库 > [LeetCode]Count Primes

[LeetCode]Count Primes

 题目:Count Primes

统计1-n的素数的个数。

思路1:

通常的思想就是遍历(0,n)范围内的所有数,对每个数i再遍历(0,sqrt(i)),每个除一遍来判断是否为素数,这样时间复杂度为O(n*sqrt(n))。

具体实现不在贴代码,过程很简单,两重循环就可以解决。但是效率很差,n较大时甚至会花几分钟才能跑完。

思路2:

用埃拉特斯特尼筛法的方法来求素数,时间复杂度可以达到O(nloglogn)。

首先开一个大小为n的数组prime[],从2开始循环,找到一个质数后开始筛选出所有非素数;

筛选方法如下:

1.如果i是素数,则从i*i开始筛选,因为2-i在外循环为2-i的时候已经筛选过了;

2.筛选掉所有i的倍数的数,即:将prime[k*i] = false;(i < k < n/i)

思路并不复杂,网上有先将数组分成奇偶再避开偶数,但是这里当外循环开始为2时,内循环从2^2=4开始会把所有的偶数筛掉。

/**埃氏筛O(nloglogn)**/
int LeetCode::countPrimes(int n){
    if (n < 1)return 0;
    vector<bool>prime(n + 1,true);
    prime.at(0) = false;
    prime.at(1) = false;
    int count = 0;
    for (size_t i = 2; i < n; i++){
        if (prime.at(i)){
            ++count;
            //从i*i开始筛选,应为2*i、3*i在i为2、3时已经被筛选过;这里是为了筛掉质数i的倍数
            for (size_t j = i*i; j <= n; j += i)prime.at(j) = false;
        }
    }
    return count;
}

思路3:

线性欧拉筛,时间复杂度O(n)。

上面的筛选法,仔细想想会发现有的合数被重复筛除,例如30,2*15筛了一次,5*6重复筛除,所以也就有了欧拉线性筛法。

首先,先明确一个条件,任何合数都能表示成一系列素数的积。

然后利用了每个合数必有一个最小素因子,每个合数仅被它的最小素因子筛去正好一次。所以为线性时间。

/**线性欧拉筛O(n)**/
int LeetCode::countPrimes2(int n){
    if (n < 1)return 0;
    vector<bool>flag(n + 1, true);
    vector<int>prime;//保存所有的素数
    flag.at(0) = false;
    flag.at(1) = false;
    int count = 0;
    for (size_t i = 2; i < n; i++){
        if (flag.at(i)){//记录素数的个数
            ++count;
            prime.push_back(i);
        }
        //任何合数都能表示成一系列素数的积,然后利用了每个合数必有一个最小素因子,每个合数仅被它的最小素因子筛去正好一次。所以为线性时间。
        for (size_t j = 0; j < count && i*prime.at(j) < n; j++){
            flag.at(i*prime.at(j)) = false;//素数的倍数
            if (!(i % prime.at(j)))break;//保证每个数只被最小素数筛选一次
        }
    }
    return count;
}

if (!(i % prime.at(j)))break;//保证每个数只被最小素数筛选一次

prime数组中的素数是递增的,当 i 能整除 prime[j],那么 i*prime[j+1] 这个合数肯定被 prime[j] 乘以某个数筛掉。

因为i中含有prime[j], prime[j] 比 prime[j+1] 小。接下去的素数同理。所以不用筛下去了。

在满足i%prme[j]==0这个条件之前以及第一次满足改条件时,prime[j]必定是prime[j]*i的最小因子。

还不清楚的可以参考一下这篇博客:http://blog.csdn.net/nk_test/article/details/46242401

 

[LeetCode]Count Primes