素数检测的几种算法
素数，又称质素，除了能表示为它本身和1的乘积以为，不能表示为任何其它两个整数的乘积。
一、 试除法
根据素数的定义，假设要判断的自然数为n，那么最简单的方法便是用2~（n-1）之间的数字依次枚举试除一遍，如果能整除，那说明这个数不是素数，显然，此种算法的效率极低。初学C语言的人会使用另一种改进的试除法，那便是除数不用取遍2~（n-1），而是取2~(int)sqrt(n)，但是当n很大时，此种算法的时间消耗也很大，也是不可取的。
二、 筛选法
筛选法事一种比较高校的判断素数的方法，能够一次性的筛选除某个区间的素数。算法的基本原理也是利用了素数的定义，在某个范围内，依次去掉2的倍数，3的倍数，5的倍数……以此类推，一直到所有小于或等于n的数字的倍数都被去掉为止。这就像一面筛子，把某个区间范围内满足条件的数留下来，其余的数字去掉，最后判断此区间内的某个数是否为素数时，时间
复杂度就为O（1）。很显然，时间的主要消耗都在于数字的筛选上。利用给数组单元置零的方法来实现，创建一个数组a[i]，i=1、2、3……，用memset()函数将其全部置1，当i不是素数，则将a[i]置零。
代码实现如下：
#define MAX N  /*N为设置的某个数，确定一个判断区间*/
int isprime[MAX];
void is_prime1()
{
    int i,j;
    memset(isprime,1,sizeof(isprime));
    for(i=2;i<MAX;i++)
    {
        if(isprime[i])
          for(j=2*i;j<MAX;j+=i)
              isprime[i]=0;
    }
}
   
此种筛选算法可以优化为二次筛选，就是要求n以内的素数，就先把sqrt(n)内的素数求出来，再用已经求得的素数来筛选后面的合数。
2007年，复旦的xreborner将筛选法进一步改进为真正的线性时间复杂度，改进算法是增加了一个数组，记录已经到的素数，通过这些已经到的素数，来筛掉后面的数。
三、 费马测试
    费马算法是利用数学结论来进行素数检验的方法，利用了费马定理得到推论，若n>1,存在，使得，则是合数。费马算法正是利用这个推论判断合数，对于素数的判断和可靠性的判断依据以下定理：
定理：或者所有的或者之多一半的满足  和（a,n）=1的整数a满足。
费马测试是判断一个数是否为素数的一个基于概率的测试。费马测试的具体实现是，对于n，从素数表中取出任意的素数对其进行费马测试，如果取了很多个素数，n仍未测试失败，那么则认为n是素数。当然，测试的次数越多越准确，但一般来讲50次就足够了。另外，预先构造一个包括500个素数的数组，先对n进行整除测试，将会大大提高通过率。
代码实现如下：
int montgomery(int n,int p,int m)
{
    int k=1;
    n%=m;
    while(p!=1)
    {
        if(0!=(p&1))
            k=(k*n)%m;
        n=(n*n)%m;
        p>>1;
    }
    return(n*k)%m;
}
void prime(int n)
{
    np=0;
    for(int i=2;i<=n;i++)
    {
        if(!isprime[i])p[np++]=i;
    for(int j=0;j<np&&p[j]*i<=n;j++)
    {
        isprime[p[j]*j]=1;
        if(i%p[j==0])break;
      }
      }
}
bool isprime(int n)
{
    if(n<2)return false;
    for(int i=0;i<np;++i)
    {
        if(1!=montgomery(p[i],n-1,n))
c++判断素数        {
            return false;
          }
      }
      return true;
}
四、 米勒-拉宾测试
    米勒拉宾测试是一个不确定的算法，只能从概率意义上判定一个数可能是素数。
      输入奇数n，判断n为素数或者合数。
      步骤：
1. 计算r和R,使得，R奇。
2. 随即选择a,。
3. for i=0 to r，计算。
4. 若，则输入合数。
5. 若，则输入素数。
6. 设j=max{i: },则输入素数。
7. 若，则输出素数，否则输出合数。
代码如下：
long long pow_mod(long long bs,long long power,long long diver)
{
    if(power==o)return(1);
    else if(power==1)return(bs);
    else if((power&1)==o)
    return(pow_mod(bs*bs%diver,(power>>1),diver));
    else return(pow_mod(bs*bs%diver,power/2,diver)*bs%diver);
}
bool M_R(long long base,long long num)
{
    d=num-1;
    while((d&1)==0)
    {
        d=(d>>1);
    }
    if((pow_mod(base,d,num)==1)||(pow_mod(base,d,num)==num-1))
    return true;
    else
    {
        t=(num-1)/2;
        while(d!=t)
        {
            d=(d<<1);
            if(pow_mod(base,d,num)==num-1)return true;
          }
          return false;
    }
}
五、 AKS算法
    2002年提出的AKS算法，利用了代数数论、有限域中的深刻结论，是一个确定性的多项式算法。ASK算法描述如下：
输入奇数n，判断n为素数或者合数。
步骤：
1. 输入n>1;
2. 若，输出合数；
3. r>0,满足；
4. 任意的，计算（a,n）,如果n>(a,n)>1,则输出合数；
5. ，输出素数；
6. FOR a=1 to,输出合数。
7. 输出素数。
以上的介绍可见，素数的判断有许多方法，在数字规模不同的情况下，可以选择不同的算法。筛选法容易理解，一定程度上效率得到提高，可是却受到内存的限制，而米勒拉宾算法是一种不确定算法，却是高效算法。AKS算法又给我们打开了一个新境界，更多的启发，相信在今后的分析研究中，将有更高效的算法出现。
参考文献
[1]刘汝佳，《算法艺术与信息学竞赛》
[2]Joseph.H.Silverman,A Friendly Introduction to Number Theory(Third Edition),China Machine Press
[3]张四兰等，《可信赖的高效素数生成和检验算法》

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。