筛选法求素数

本文格式为Word版，下载可任意编辑——筛选法求素数

用筛选法求素数

质数算法大全，质数算法大全，及C程序实现优化详解筛选法三木追风质数的定义一个数，假使只有1和它本身两个因数，这样的数叫做质数，又称素数。在上文《素数算法大全，及C程序实现优化详解(一)试除法》中我们已经探讨了求解素数的一类算法，并且将试除法从最初的低效版本优化的高效的V2。那么，还有没有其它更佳算法呢？这就是下面三藏要和大家探讨的内容合数过滤筛选法算法描述：素数N不能被2~(N-1)间的任何数整除；反过来看，只要能被2~(N-1)算法描述我们知道，间的任何数整除的N，都不是素数。所以我们可以采用一个简单的排除法：就是对N以内的所有数，只要逐个去除值为2~(N-1)的倍数的数，剩下的就是素数。C语言实现//合数过滤筛选法Ver1//参数：n求解n以内(包括n)的素数//返回值：n以内素数个数intCompositeNumFilterV1(intn){inti,j;//素数数量统计intcount=0;//分派素数标记空间，结合后文思考为何+1char*flag=(char*)malloc(n+1);//初始化素数标记for(i=2;i=n;i++)

用筛选法求素数

{//为什么*(p+i)要写成flag[i]呢？可读性更佳尔flag[i]=1;}//写程序要注意排版和留空，便利阅读，也可减少出错几率//以2~(N-1)为因子过滤合数for(i=2;in;i++){for(j=2;i*j=n;j++){//i*j是由i,j两整数相乘而得，显然不是素数flag[i*j]=0;}}//统计素数个数for(i=2;i=n;i++){//其实if(flag)就其同样作用了，但这么写是有留言的//请参阅《C语言程序设计常见错误剖析及解决之道》一文if(1==flag[i])count++;}//因输出费时，且和算法核心相关不大，故略//释放内存，别忘了传闻中的内存泄漏free(flag);returncount;}在上文给出的main函数中以不同参数调用CompositeNumFilterV1函数，得到执行结果如下：[100000]以内素数个数：9592,计算用时：15毫秒[1000000]以内素数个数：78498,计算用时：125毫秒[5000000]以内素数个数：348513,计算用时：2578毫秒[10000000]以内素数个数：664579,计算用时：6281毫秒

用筛选法求素数

注：因程序是非独占性运行的，所以时间不是完全确切的，但基本能反映实情显然，比上文中的试除法要快，而且谁都可以看到上例是一个未经优化的粗陋版本，好多地方是三藏有意采用比较低效做法，为了与后文的优化版比较，凸显优化之重要，也为了初学者记住别采用类似低效做法，下面我们开始优化之旅优化分析上面CompositeNumFilterV1函数存在的问题有：1.在外层循环，需要一直执行到n-1吗？不要，由于n/2~n-1间的数显然不能整出n2.在内层循环中重复使用i*j显然是低效的，考虑到计算机中加减运算速度比乘除快，可以考虑变乘法为加法3.在循环修改flag过程中，其实有好多数会被重复计算若干次，譬如6=2*3=3*2，会被重复置0，类似操作好多，所以我们得设法避免或减少flag重复置0据上述分析，我们可将程序优化如下：//合数过滤筛选法Ver2//参数：n求解n以内(包括n)的素数//返回值：n以内素数个数intCompositeNumFilterV2(intn){inti,j;//素数数量统计intcount=0;//分派素数标记空间，明白+1原因了吧，由于浪费了一个flag[0]char*flag=(char*)malloc(n+1);//初始化素数标记，要高效点咯flag[2]=1;//注意是in不是上例中的i=n了，理由自思for(i=3;in;i++){flag[i++]=1;//偶数自然不是素数，直接置0好了flag[i]=0;}//n为奇数if(n%2!=0)

用筛选法求素数

{flag[n]=1;}//从3开始filter，由于2的倍数早在初始化时代就干掉了//到n/2止的理由还要说吗for(i=3;i=n/2;i++){//i是合数，请歇着吧，由于您的工作早有您的质因子代劳了if(0==flag[i])continue;//从i的2倍开始过滤，变乘法为加法for(j=i+i;j=n;j+=i){flag[j]=0;}}//统计素数个数for(i=2;i=n;i++){if(flag[i])count++;}//因输出费时，且和算法核心相关不大，故略//释放内存，别忘了传闻中的内存泄漏free(flag);returncount;}再来调用CompositeNumFilterV2得到执行结果：[100000]以内素数个数：9592,计算用时：n太小，时间精度不够[1000000]以内素数个数：78498,计算用时：31毫秒[5000000]以内素数个数：348513,计算用时：453毫秒[10000000]以内素数个数：664579,计算用时：1062毫秒[100000000]以内素数个数：5761455,计算用时：12973毫秒

用筛选法求素数

哇哇，比昨天的试除发快了好多倍，可见算法的威力，值得好好学习，别说学算法没用咯。上例着那个计算一亿以内的素数只要约13秒，应当算不错了，今天是否可以休息了呢？No，我们要追求极限！intCompositeNumFilterV3(intn){inti,j;//素数数量统计intcount=0;//分派素数标记空间，明白+1原因了吧，由于浪费了一个flag[0]char*flag=(char*)malloc(n+1);//干嘛用的，请细心研究下文intmpLen=2*3*5*7*11*13;charmagicPattern[mpLen];//奇怪的代码，why，思考无法代劳，想！for(i=0;impLen;i++){magicPattern[i++]=1;magicPattern[i++]=0;magicPattern[i++]=0;magicPattern[i++]=0;magicPattern[i++]=1;magicPattern[i]=0;}for(i=4;i=mpLen;i+=5)magicPattern[i]=0;for(i=6;i=mpLen;i+=7)magicPattern[i]=0;for(i=10;i=mpLen;i+=11)magicPattern[i]=0;for(i=12;i=mpLen;i+=13)magicPattern[i]=0;//新的初始化方法,将2,3,5,7,11,13的倍数全干掉//而且采用memcpy以mpLen长的magicPattern来批量处理intremainder=n%mpLen;char*p=flag+1;char*pstop=p+n-remainder;

用筛选法求素数

while(ppstop){memcpy(p,magicPattern,mpLen);p+=mpLen;}if(remainder0){memcpy(p,magicPattern,remainder);}flag[2]=1;flag[3]=1;flag[5]=1;flag[7]=1;flag[11]=1;flag[13]=1;//从17开始filter，由于2,3,5,7,11,13的倍数早被kill了//到n/13止的，哈哈，少了好多吧intstop=n/13;for(i=17;i=stop;i++){//i是合数，请歇着吧，由于您的工作早有您的质因子代劳了if(0==flag[i])continue;//从i的17倍开始过滤intstep=i*2;for(j=i*17;j=n;j+=step){flag[j]=0;}}//统计素数个数for(i=2;i=n;i++){if(flag[i])count++;}//因输出费时，且和算法核心相关不大，故略

用筛选法求素数

//释放内存，别忘了传闻中的内存泄漏free(flag);returncount;}再看Com