注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

yeye55的博客

编程就象品一杯清茶,清淡却又深厚。

 
 
 

日志

 
 
关于我

宅男一只,喜欢编程。没事的时候就喜欢抱着电脑看看电影、看看动漫、听听音乐、打打网游、逛逛论坛。清静的时候喜欢专研编程技术,但是发现自己至今仍然只是一只三脚猫。

网易考拉推荐

求不小于(大于)N的最小(最大)质数  

2011-11-04 10:56:37|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

  本文最早于2008年12月17日在编程论坛(programbbs.com)上发表,页面地址:http://programbbs.com/bbs/view12-16614-1.htm 。

  前几天遇到一个问题:要求一个不小于N的最小质数,或者是求一个不大于N的最大质数。例如不小于100的最小质数为101,不大于100的最大质数为97,不小于199的最小质数为199,不大于199的最大质数为199,因为199本身就是质数。查了许多资料想到了一个算法:先利用埃拉托斯特尼筛选法求出不大于N的所有质数,把这些质数存入一个Integer数组,如果是求一个不大于N的最大质数,那么数组的最后一个元素就是结果可以返回。如果是求一个不小于N的最小质数,当数组最后一个元素等于N,那么N就是结果可以返回,如果不等于就从N+1的数开始寻找一个质数,寻找时利用数组中的质数是否可以整除待确定的数,来判断待确定的数是否是一个质数。

  埃拉托斯特尼筛选法的具体实现是:先把N个自然数按次序排列起来。1不是质数,也不是合数,筛除掉;第二个数2是质数保留下来,然后把2后面能被2整除的数都筛除掉;2后面第一个没被筛除的数是3,把3保留下来,再把3后面所有能被3整除的数都筛除掉;3后面第一个没被筛除的数是5,把5保留下来,再把5后面所有能被5整除的数都筛除掉……。就这样一直做下去,把不大于N的全部合数都筛除掉,留下的就是不大于N的全部质数。我实现埃拉托斯特尼筛选法的算法是:首先从2开始到N的自然数(2,3,4,……,N)每个数都对应一个二进制位,当一个数对应的二进制位为1时表示该数被保留,反之为0时表示该数被筛除。利用一个Cardinal数组保存所有的二进制位,数组0号元素的32个位从低位开始分别对应自然数:2,3,4,……,34,并以此类推,将从2开始到N的自然数对应的二进制位保存在数组中。最后利用位运算进行筛除。具体的代码如下:

//埃拉托斯特尼筛选法求N以内的所有质数,返回质数个数
function Eratosthenes(N : Integer; var E  : TIntegerDynArray): Integer;
var
    F : array of Cardinal;
    i,m,Off,Len,FLen :  Integer;
begin
    if N<2 then
    begin
         SetLength(E,0);
         result:=0;
         exit;
    end;
    //初始化
    Len:=N-1;
    FLen:=(Len shr 4)+1;
    SetLength(F,FLen);
    for i:=0 to FLen-1 do  F[i]:=$FFFFFFFF;
    //筛查
    i:=0; result:=N-1;
    while i<Len do
    begin
         m:=i+2;
         Off:=i+m;
         while Off<Len do
         begin
             if (F[Off shr 4] and (1 shl (Off and $F)))<>0 then
             begin
                 F[Off shr 4]:=F[Off shr 4]-(1 shl (Off and $F));
                 result:=result-1;
             end;
             Off:=Off+m;
         end;
         for i:=i+1 to Len-1 do
             if (F[i shr 4] and (1 shl (i and $F)))<>0 then break;
    end;
    //拷贝数据
    SetLength(E,result);
    Off:=0;
    for i:=0 to Len-1 do
    begin
         if (F[i shr 4] and (1 shl (i and $F)))<>0 then
         begin
             E[Off]:=i+2;
             Off:=Off+1;
         end;
    end;
    SetLength(F,0);
end;

  利用上面的算法求不小于(大于)N的最小(最大)质数,当判断大于N的最小质数时由于已经可以排除2,而大于2的所有质数都是奇数,于是可以只从奇数中寻找。具体的代码如下:

//当Min=true时返回不小于N的最小质数
//当Min=false时返回不大于N的最大质数
function PrimeNumber(N : Integer; Min :  Boolean): Integer;
var
    E : TIntegerDynArray;
    m,i : Integer;
    b : Boolean;
begin
    m:=Eratosthenes(N,E);
    if m=0 then
    begin
         result:=2;
         exit;
    end;
    if E[m-1]=N then
    begin
         result:=N;
         SetLength(E,0);
         exit;
    end;
    if not Min then
    begin
        result:=E[m-1];
         SetLength(E,0);
         exit;
    end;
    if (N and 1)<>0  then
         result:=N+2  //奇数
    else
         result:=N+1; //偶数
    while true do
    begin
         b:=true;
         for i:=1 to m-1 do
             if (result mod E[i])=0 then
             begin
                 b:=false;
                 break;
             end;
         if b then break;
         result:=result+2;
    end;
    SetLength(E,0);
end;

  以上算法利用的是埃拉托斯特尼筛选法,利用位运算进行筛除的部份如果改写成内嵌汇编的话性能可能会更好,本人的汇编语言很差所以没办法写出来。另外埃拉托斯特尼筛选法对于1000000以内的质数还是很快的,但对于大于1000000的质数速度较慢,不知各路高手还有没有更好的算法?

  根据上述算法我写出来的程序如下:

  上述程序在我的电脑上的测试数据如下:

运行耗时:31  毫秒
不小于  1000000 的最小质数为  1000003
运行耗时:813  毫秒
不小于  10000000 的最小质数为  10000019
运行耗时:10109  毫秒
不小于  100000000 的最小质数为  100000007
运行耗时:163953  毫秒
不小于  1000000000 的最小质数为  1000000007

  项目文件下载(点这里

  可执行文件下载(点这里

  评论这张
 
阅读(1228)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017