首页 > 代码库 > [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