顺便学习了下线性筛(欧拉筛):
http://www.cnblogs.com/zhuohan123/p/3233011.html
http://blog.csdn.net/leolin_/article/details/6642126
Eratosthennes筛法时间复杂度为O(nlogn),用每一个素数去筛它的倍数,即筛去它的合数,显然这样有些合数被重复筛了很多次,如果能保证每个合数只被筛一次(只被枚举一次),那就可以O(n)了。
一个定理:任何一个合数都可以表示成一个质数和一个数的乘积
这是显然的。用唯一分解定理就可以证明了。
线性筛(欧拉筛)就是利用了这个定理,对于每一个合数,我们只用它最小的质因子去筛它。为了达到这个目的,循环的顺序就至关重要。
我们先从小到大枚举所有数,然后再从小到大枚举所有已经找到的质数(这个质数自然<=这个数)
然后筛掉i*prime[j]。
如果只是这样做那么时间复杂度为O(∑i/lni),不会算。。。只知道实际时间和Eratosthennes筛法差不多。
但是如果我们在第二层循环中加一句:
if(i%prime[j]==0)break; 那么不但正确性可以保证,而且时间复杂度降为O(n)。正确性:
1、保证每个合数依然还是会被筛掉。
退出后,我们少筛了i*prime[j+k],1<=k,即没有用prime[j+k]去筛这个合数。
由 i%prime[j]==0 得: i*prime[j+k]=(prime[j]*x)*prime[j+k]=prime[j]*(x*prime[j+k]),其中x是某个正整数。
即i*prime[j+k]这个合数可以被一个更小的质数prime[j]筛掉,所以以后枚举到更大的i时一定也会筛掉这个合数。
2、保证每个合数能被及时的筛掉。
这句话的意思是说,如果不能及时筛掉的话,我们就会误认为它是质数,然后把它误加入到素数表中。
如果这个数是个合数,根据唯一分解定理,一定能分解成多个n个素数的乘积,n>=2,那么这个合数之前肯定会被它最小的那个素因子筛掉。
时间复杂度:
每个合数会且仅会被最小的素因子筛去,而且只枚举一遍,所以总的时间复杂度为O(n)。
还有一些值得注意的东西:
虽然说Eratosthennes筛法时间复杂度为O(nlogn),但更准确的说法应该是Eratosthennes筛法时间复杂度介于O(n)和O(nlogn)之间,因为O(nlogn)的算法是不带任何优化的,优化后的代码在实战中效果很好,当n=1e6时,非线性部分带来的差距只有2~3倍。不带break语句的线性筛也是这个复杂度,即只比线性的增长快一点,只不过线性算法就是纯纯的O(n)了。详见紫书P312上时间复杂度的分析吧。
一些思考过程中用来分析的代码
#include <cstring> #include<stdio.h> #include<math.h> using namespace std; const int maxn = 1e8; int sb; int cnt; int prime[maxn],primesize,phi[maxn]; bool isprime[maxn]; void getlist(int listsize) { memset(isprime,1,sizeof(isprime)); isprime[1]=false; for(int i=2;i<=listsize;i++) { if(isprime[i])prime[++primesize]=i; for(int j=1;j<=primesize&&i*prime[j]<=listsize;j++) { cnt++; if(isprime[i*prime[j]]==false) sb++; isprime[i*prime[j]]=false; //if(i%prime[j]==0)break; } //puts(""); } printf("计算量:%d\n",cnt); printf("重复数:%d\n",sb); printf("质数个数:%d\n",primesize); } void print() { for(int i=0;i<primesize;i++) printf("%d\n",prime[i]); } void eratosthenes(int n) { for(int i=2;i<n;i++) isprime[i]=1; int m=sqrt(n+0.5); for(int i=2;i<=m;i++) { if(isprime[i]) { prime[++primesize]=i; for(int j=2*i;j<n;j+=i) { cnt++; if(isprime[j]==0) sb++; isprime[j]=0; } } } printf("计算量:%d\n",cnt); printf("重复数:%d\n",sb); printf("质数个数:%d\n",primesize); } int main() { //getlist(1000000); eratosthenes(100000000); //print(); return 0; }