算法小结：判断一个数是否为素数

算法总结：判断一个数是否为素数

1.约定x%y为x取模y，即x除以y所得的余数，当x<y时，x%y=x，所有取模的运算对象都为整数。
x^y表示x的y次方。乘方运算的优先级高于乘除和取模，加减的优先级最低。
见到x^y/z这样，就先算乘方，再算除法。
A/B，称为A除以B，也称为B除A。
若A%B=0，即称为A可以被B整除，也称B可以整除A。
A*B表示A乘以B或称A乘B，B乘A，B乘以A……都一样。

复习一下小学数学
公因数：两个不同的自然数A和B，若有自然数C可以整除A也可以整除B，那么C就是A和B的公因数。

公倍数：两个不同的自然数A和B，若有自然数C可以被A整除也可以被B整除，那么C就是A和B的公倍数。

互质数：两个不同的自然数，它们只有一个公因数1，则称它们互质。

费马是法国数学家，又译“费尔马”，此人巨牛，他的简介请看下面。不看不知道，一看吓一跳。

费马人物简介：http://baike.baidu.com/view/6303430.htm?fromId=5194&redirected=seachword　　

2.费马小定理：有N为任意正整数，P为素数，且N不能被P整除（显然N和P互质），则有：N^P%P=N(即：N的P次方除以P的余数是N)。

但是我查了很多资料见到的公式都是这个样子：

(N^(P-1))%P=1后来分析了一下，两个式子其实是一样的，可以互相变形得到。

原式可化为：(N^P-N)%P=0(即：N的P次方减N可以被P整除，因为由费马小定理知道N的P次方除以P的余数是N)把N提出来一个，N^P就成了你N*(N^(P-1))，那么(N^P-N)%P=0可化为：

(N*(N^(P-1)-1))%P=0
请注意上式，含义是：N*(N^(P-1)-1)可以被P整除

又因为N*(N^(P-1)-1)必能整除N（这不费话么!）
所以，N*(N^(P-1)-1)是N和P的公倍数，小学知识了^_^

又因为前提是N与P互质，而互质数的最小公倍数为它们的乘积，所以一定存在

正整数M使得等式成立：N*(N^(P-1)-1)=M*N*P
两边约去N，化简之：N^(P-1)-1=M*P
因为M是整数，显然：N^(P-1)-1)%P=0即：N^(P-1)%P=1
============================================

3.积模分解公式

先有一个引理，如果有：X%Z=0，即X能被Z整除，则有：(X+Y)%Z=Y%Z
设有X、Y和Z三个正整数，则必有：(X*Y)%Z=((X%Z)*(Y%Z))%Z

想了很长时间才证出来，要分情况讨论才行：

1.当X和Y都比Z大时，必有整数A和B使下面的等式成立：
X=Z*I+A（1）
Y=Z*J+B（2）
不用多说了吧，这是除模运算的性质！
将（1）和（2）代入(X*Y)modZ得：((Z*I+A)(Z*J+B))%Z乘开，再把前三项的Z提一个出来，变形为：(Z*(Z*I*J+I*A+I*B)+A*B)%Z（3）

因为Z*(Z*I*J+I*A+I*B)是Z的整数倍……晕，又来了。
概据引理，（3）式可化简为：(A*B)%Z又因为：A=X%Z，B=Y%Z，代入上面的式子，就成了原式了。

2.当X比Z大而Y比Z小时，一样的转化：
X=Z*I+A
代入(X*Y)%Z得：
(Z*I*Y+A*Y)%Z
根据引理，转化得：(A*Y)%Z
因为A=X%Z，又因为Y=Y%Z，代入上式，即得到原式。
同理，当X比Z小而Y比Z大时，原式也成立。

3.当X比Z小，且Y也比Z小时，X=X%Z，Y=Y%Z，所以原式成立。
=====================================================

4.快速计算乘方的算法

如计算2^13，则传统做法需要进行12次乘法。

bool RabbinMillerTest( unsigned n ){    if (n<2)    {          // 小于2的数即不是合数也不是素数        throw 0;    }    const unsigned nPrimeListSize=sizeof(g_aPrimeList)/sizeof(unsigned);//求素数表元素个数    for(int i=0;i<nPrimeListSize;++i)    {        // 按照素数表中的数对当前素数进行判断        if (n/2+1<=g_aPrimeList[i])        {            // 如果已经小于当前素数表的数，则一定是素数            return true;        }        if (0==n%g_aPrimeList[i])        {            // 余数为0则说明一定不是素数            return false;        }    }    // 找到r和m，使得n = 2^r * m + 1;    int r = 0, m = n - 1; // ( n - 1 ) 一定是合数    while ( 0 == ( m & 1 ) )    {        m >>= 1; // 右移一位        r++; // 统计右移的次数    }    const unsigned nTestCnt = 8; // 表示进行测试的次数    for ( unsigned i = 0; i < nTestCnt; ++i )    {         // 利用随机数进行测试，        int a = g_aPrimeList[ rand() % nPrimeListSize ];        if ( 1 != Montgomery( a, m, n ) )        {            int j = 0;            int e = 1;            for ( ; j < r; ++j )            {                if ( n - 1 == Montgomery( a, m * e, n ) )                 {                    break;                }                e <<= 1;            }            if (j == r)            {                return false;            }        }    }    return true;}

以上内容载自博客园并稍加编辑：http://www.cnblogs.com/Knuth/archive/2009/09/04/1559949.html

查看更多 下一篇