素数检测算法

素数检测的几种算法素数，又称质素，除了能表示为它本身和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]置零。代码实现如下：#defineMAXN/*N为设置的某个数，确定一个判断区间*/intisprime[MAX];voidis_prime1()(inti,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,存在1Ja<n-1,使得"i丰1(modn)，则是合数。费马算法正是利用这个推论判断合数，对于素数的判断和可靠性的判断依据以下定理：定理：或者所有的或者之多一半的满足1<a<n-1和(a,n)=1的整数a满足an-1三1(modn)。费马测试是判断一个数是否为素数的一个基于概率的测试。费马测试的具体实现是，对于n，从素数表中取出任意的素数对其进行费马测试，如果取了很多个素数，n仍未测试失败，那么则认为n是素数。当然，测试的次数越多越准确，但一般来讲50次就足够了。另外，预先构造一个包括500个素数的数组，先对n进行整除测试，将会大大提高通过率。代码实现如下：intmontgomery(intn,intp,intm)(intk=1;n%=m;while(p!=1)(if(0!=(p&1))k=(k*n)%m;n=(n*n)%m;p>>1;}return(n*k)%m;}voidprime(intn)(np=0;for(inti=2;i<=n;i++)(if(!isprime[i])p[np++]=i;for(intj=0;j<np&&p[j]*i<=n;j++)(isprime[p[j]*j]=1;if(i%p[j==0])break;}}}boolisprime(intn)(if(n<2)returnfalse;for(inti=0;i<np;++i)(if(1!=montgomery(p[i],n-1,n))returnfalse;}returntrue;}四、米勒-拉宾测试米勒拉宾测试是一个不确定的算法，只能从概率意义上判定一个数可能是素数。输入奇数n,判断n为素数或者合数。步骤：计算r和R,使得n-1=2rR，r奇。随即选择a,ae乙\{0}。fori=0tor，计算b=a2rRo若aR=bu1(modn)，则输入合数。若aR=b三1(modn)，则输入素数。设j=max{i:b.公1(modn)}，则输入素数。若b三-l(modn)，则输出素数，否则输出合数。代码如下：longlongpow_mod(longlongbs,longlongpower,longlongdiver)(if(power==o)return(1);elseif(power==1)return(bs);elseif((power&1)==o)return(pow_mod(bs*bs%diver,(power>>1),diver));elsereturn(pow_mod(bs*bs%diver,power/2,diver)*bs%diver);}boolM_R(longlongbase,longlongnum)(d=num-1;while((d&1)==0)(d=(d>>1);}if((pow_mod(base,d,num)==1)||(pow_mod(base,d,num)==num-1))returntrue;elset=(num-1)/2;while(d!=t)(d=(d<<1);if(pow_mod(base,d,num)==num-1)returntrue;}returnfalse;}}五、AKS算法2002年提出的AKS算法，利用了代数数论、有限域中的深刻结论，是一个确定性的多项式算法。ASK算法描述如下：输入奇数n，判断n为素数或者合数。步骤：输入n>1;若n=ak，输出合数；找r>0,满足o(n)>4log2n；任意的0<a<r，计算(a,n)，如果n>(a,n)>1,则输出合数；n<r，输出素数；FORa=1to2®(x)logn■(x+a)n-(xn+a)。o(modxr-1,n)，输出合数。输出素数。以上的介绍可见，素数的判断有许多方法，在数字规模不同的情况下，可以选择不同的算法。筛选法容易理解，一定程度上效率得到提高，可是却受到内存的限制，而米勒拉宾算法是一种不确定算法，却是高效算法。AKS算法又给我们打开了一个新境界，更多的启发，相信在今后的分析研究中，将有更高效的