素数判断的几种方法代码实现及其复杂度分析_素数测试 时间复杂度

 素数判断的几种方法代码实现及其复杂度分析 

 

一、 朴素判断素数

根据素数的定义，约数只有1和它本身的整数称为素数，假设一个整数为n，于是最朴素的判断n是否为素数的方法就是从2到n-1都枚举一遍，判断是否存在能整除n的整数，如果都不能则n为素数。

代码实现如下：

bool Brute_Force(int n)
{
    for (int i=2; i<=n-1; i++)
        if (n%i==0) return false;
    return true;
}

此函数返回true则说明n为素数，反之不是。

很容易发现，这种方法判断素数，对于一个整数n,需要n-2次判断，时间复杂度为O(n)的。在n非常大或者测试量很大时，这种方法显然是不可取的。

二、 改进朴素判断素数

 

对于一个小于n的整数x，如果n不能整除x，则n必然不能整除n/x。反之相同。所以我们按照素数定义来判断素数时，可以进行一个较为明显的优化。即我们只需从2枚举到√n即可。因为在判断2的同时也判断了n/2……以此类推，到√n时就把2到n-1的数都判断过了。

代码实现如下：

bool Brute_Force2(int n)
{
    for (int i=2; (__int64)i*i<=n; i++)
        if (n%i==0)
            return false;
    return true;
}

这里使用i*i<=n来取代i<=√n

是为了避免是用sqrt()函数，其消耗时间很大，在大量数据测试中时间消耗很明显。同时强制转换i成__int64类型是为了防止i*i在int范围内溢出。此算法的时间复杂度也很容易得出，对于一个整数n，需要测试√n-1次，所以本算法的时间复杂度为O(√n)的。

三、 标准的爱拉托逊斯筛选法

 

爱拉托逊斯筛选法（以下简称筛法），是一种高效的判断素数的方法。能够一次性的筛选出某个区间的素数。其算法原理本质还是充分利用了素数的定义，即素数的约数只有1和它本身。如果某个数m是另一个数n的倍数，则说明m肯定不是素数。所以我们只要在某个范围内，将已知素数的所有倍数都筛去，剩下的肯定是素数。因为只有它不是其他数的倍数（1和本身除外）。

具体做法是：先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。第二个数2是质数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去。这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。因为希腊人是把数写在涂腊的板上，每要划去一个数，就在上面记以小点，寻求质数的工作完毕后，这许多小点就像一个筛子，所以就把埃拉托斯特尼的方法叫做“埃拉托斯特尼筛”，简称“筛法”。（另一种解释是当时的数写在纸草上，每 要划去一个数，就把这个数挖去，寻求质数的工作完毕后，这许多小洞就像一个筛子。）

代码实现如下：

#define MAX 10007
bool isprime[MAX];     
void TheSieveofEratosthees()
{
    int i,j;
    for (i=2; i<MAX; i++)
        isprime[i]=1;
    for (i=2; i<MAX; i++)
    {
        if (isprime[i])
            for (j=i+i; j<MAX; j+=i)
                isprime[j]=0;
    }
}

在执行完本算法后，isprime[i]=1则说明i是素数。所以本算法在执行完一遍后，就能在O(1)的时间复杂度内判断MAX以内的任意数是否为素数。所以整个算法的时间消耗都在筛法的效率上。乍看筛法的时间复杂度貌似是O(n^2)的，但是其实不然，第二个循环中，每次递增的i，当i越来越大时，j很快就能超过M。其实筛法的实际复杂度是的，在可以测试的范围内，其实是接近线形的，虽然实际上不是。这个是筛法的精妙所在。

四、 改进的爱拉托逊斯筛选法

 

理论上筛法在可以测试的范围内，已经接近线性的复杂度了，对于一般的需要来说，已经没有什么必要去优化筛法了。但是为了更深入或者满足更苛刻的效率要求，标准的筛法还是有可以改进的地方的，使得筛法在常数级别上得到降低。实际上在2007年，复旦的xreborner已经将筛法改进为真正的线性时间复杂度。

 

法是增加了一个数组，记录已经找到的素数，通过这些已经找到的素数，来筛掉后面的数，由于每个数都能分解成质因数的形式，所以所有质因数都被筛掉后，自然不在素数列表中了。

代码实现如下：

#define MAX 10007
bool isprime[MAX];
int p[MAX];
void prime(int n)
{
    memset(isprime, 0, sizeof isprime);
    memset(p, 0, sizeof p);
    int 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]*i] = 1;
            if( i % p[j] == 0) break;
        }
    }
}

这个算法的关键在于if(i%pr[j]== 0) break;。它使得任何一个合数，只被它最小的质因数标记过一次。所以整个算法是线性的。但考虑到log(log(100000000))还不到3，故这个线性算法其实也只有理论上的价值罢了。

五、 朴素判断+筛法

 

通过上面的筛法实现可以看出，用筛法直接判断素数是很有限的，筛法受内存的限制，要判断n是否为素数，需要开大小为n的bool数组。当n很大的时候，显然是不可取的。所以我们可以折中以上两种算法，将朴素判断和筛法结合在一起，使得朴素判断能得到进一步的优化。方法二中朴素判断的优化已经大大降低了复杂度。其实我们再深入理解就会发现，其实从2到√n中，也是有很多判断是没必要的，比如某个数n不能被2整除，则必然不能被4整除（其实2的倍数都不能）。所以用筛法预处理出小于√n的所有素数。这样在大量数据测试的时候效率提高很多。

代码实现如下：

void prime(int n)
{
    memset(isprime, 0, sizeof isprime);
    memset(p, 0, sizeof p);
    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]*i] = 1;
            if( i % p[j] == 0) break;
        }
    }
}
bool Brute_Force3(int n)
{
    for (int i=0; p[i]*p[i]<=n; i++)
        if (n%p[i]==0)
            return false;
    return true;
}

由以上5种方法可以看出，并不是朴素算法就一定没优点，也不是高效的筛法就很完美，有时候经过深入了解，将各种已经存在的算法组合在一起也能发挥很大的效果，从而达到优化原先算法的程度。上面的算法总时间复杂度理论上也是O(√n)的，但是常数上已经得到很大的优化，效率上比原来改进的朴素快了好几十倍之多。数据范围越大，其优化效果也明显。

六、 费马素性测试

 

费马小定理说的是：如果p是一个素数，那么对于任意一个整数a，a p − a 能被p整除，也可以用模运算表示如下：（p是素数，a是整数）这个定理又如下变式：如果p是一个素数，且整数a与p互素，那么a p−1 − 1 可以被p整除，用模运算表示如下

（p是素数，a是整数，a与p互素）、还有一种表述是：如果p是一个素数，a是一个整数且a不包含因数p，那么a p−1 −1 可以被p整除。费马小定理是费马素性测试的基础。费马在给出此定理的时候未给出证明，第一个证明其的人是Gottfried Leibniz。

费马素性测试是判断一个数是否为素数的一个基于概率的测试。事实上，费马小定理的逆否定理成立，而费马小定理的逆定理是不成立的，而费马素性测试就是基于费马小定理的“逆定理”的。大概的算法描述是，当p为奇数时（偶数特判一下就行啦，不就一个2嘛）让a在1-p之间(包括1和p）选取随机值，如果等式不成立，那么p肯定不是素数，如果成立，那么p就有较大可能是素数，我们称他为伪素数。当然，费马素性测试是有极大缺陷的，因而基本上平时没有多大用武之地。一个缺陷就是Carmichael数的存在，Carmichael数是指如果一个数n可以通过所有‘a’值的费马素性测试却并非为素数，那么就叫n为Carmichael数。这样的数随着n的增大而越来越少的，这些数中，最小的一个是561.

费马测试的具体实现是，对于N，从素数表中取出任意的素数对其进行费马测试，如果取了很多个素数，N仍未测试失败，那么则认为N是素数。当然，测试次数越多越准确，但一般来讲50次就足够了。另外，预先用“小学生”的算法构造一个包括500个素数的数组，先对Q进行整除测试，将会大大提高通过率。

 

代码实现如下：

i

int Montgomery(int n,int p,int m)
{
    //快速计算(n^e)%m的值,即逐次平方法
    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;
}
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]*i] = 1;
            if( i % p[j] == 0) break;
        }
    }
}
bool IsPrime3(int n)
{
    if ( n < 2 )   // 小于2的数即不是合数也不是素数
    {
        return false;
    }
    for (int i=0; i<np; ++i)
    {
        // 按照素数表中的数对当前素数进行判断
        if (1!=Montgomery(p[i],n-1,n))//蒙格马利算法
        {
            return false;
        }
    }
    return true;
}

 

 

七、 米勒-拉宾素性测试

 

拉宾米勒测试是一个不确定的算法，只能从概率意义上判定一个数可能是素数，但并不能确保。但是也是目前公认最高效的素性测试之一。

算法流程如下:1.选择T个随机数A，并且有A<N成立。2.找到R和M，使得N=2*R*M+1成立。快速得到R和M的方式：N用二进制数B来表示，令C=B-1。因为N为奇数（素数都是奇数），所以C的最低位为0，从C的最低位的0开始向高位统计，一直到遇到第一个1。这时0的个数即为R，M为B右移R位的值。3.如果A^M%N=1，则通过A对于N的测试，然后进行下一个A的测试4.如果A^M%N!=1，那么令i由0迭代至R，进行下面的测试5.如果A^((2^i)*M)%N=N-1则通过A对于N的测试，否则进行下一个i的测试6.如果i=r，且尚未通过测试，则此A对于N的测试失败，说明N为合数。7.进行下一个A对N的测试，直到测试完指定个数的A

通过验证得知，当T为素数，并且A是平均分布的随机数，那么测试有效率为1 / ( 4 ^ T )。如果T > 8那么测试失误的机率就会小于10^(-5)，这对于一般的应用是足够了。如果需要求的素数极大，或着要求更高的保障度，可以适当调高T的值。

 

代码实现如下：

long long Pow_mod(long long bs,long longpower,long long diver)
{
    if(power==0) return(1);
    else if(power==1) return(bs);
    else if ((power&1)==0)return(Pow_mod(bs*bs%diver,(power>>1),diver));
    elsereturn(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;
    }
}

由于能用逐次平方法在O(logn)的时间内算出a^bmod c.米勒-拉宾的算法时间主要是花在这里了，所有米勒-拉宾算法的时间复杂度是O(logn)的。

对于朴素判断优化的O(√n)要快了好多。

 

 

八、 总结与期望

 

通过以上7种判断素数方法的深入了解和代码实现，可以发现素数确实是数论中相当重要的一个组成元件。其涉及的方面相当广泛。通过以上几种方法的分析，我们能更清晰更具体的看到素数判断在不同的需求下，会有不同的算法选择。高效的筛法却不能逃避内存的限制，而米勒-拉宾测试是一种不确定的算法，有不确定性，这些都是高效算法所需要付出的代价。深入了解这些算法思想，能让我们在面对更多更难的问题时，能够冷静思考，从其定义和性质来分析，进一步分解问题，从而达到高效的解决。