如题所述
高速判断用 miller-rabin算法或者 aks 算法
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……都一样。
有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
有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
有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
先有一个引理，如果有：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，所以原式成立。
=====================================================
如计算2^13，则传统做法需要进行12次乘法。
[cpp] view plaincopyprint?- /*计算n^p*/ unsigned power(unsigned n,unsigned p) { for(int i=0;i<p;i++) n*=n; return n; }
unsigned power(unsigned n,unsigned p)
{
for(int i=0;i<p;i++) n*=n;
return n;
}
该死的乘法，是时候优化一下了！把2*2的结果保存起来看看，是不是成了：
4*4*4*4*4*4*2
再把4*4的结果保存起来：16*16*16*2
一共5次运算，分别是2*2、4*4和16*16*16*2
这样分析，我们算法因该是只需要计算一半都不到的乘法了。
为了讲清这个算法，再举一个例子2^7：2*2*2*2*2*2*2
两两分开：(2*2)*(2*2)*(2*2)*2
如果用2*2来计算，那么指数就可以除以2了，不过剩了一个，稍后再单独乘上它。
再次两两分开，指数除以2： ((2*2)*(2*2))*(2*2)*2
实际上最后一个括号里的2 * 2是这回又剩下的，那么，稍后再单独乘上它 现在指数已经为1了，可以计算最终结果了：16*4*2=128
目前为止，人们未找到一个公式可求出所有质数。也就是说遇见很大数判断是否是素数只有尝试是否能被一个素数整除。
对于较小的数可以用查表的方法进行判断，如1000以内质数表等．判断一个自然数是不是质数。
对于较大的素数还没有统一的判别方法。目前主要方法就是查“质数表”法．编制质数表的过程是：按照自然数列，第一个数1不是质数，因此要除外，然后按顺序写出2至500的所有自然数，这些数中2是质数，把它留下，把2后面所有2的倍数划去，2后面的3是质数，接着再把3后面所有3的倍数划去，如此继续下去，剩下的便是500以内的全部质数。最早使用上述方法来寻求质数的人，是古代希腊数学家埃拉托斯特尼，由于他在开始时，先把自然数写在一块蜡板上，把不是质数的数（合数）分别刺上一个孔，这样，在蜡板上就被刺上了许多象筛子一样的孔，后来，大家就把这种寻求质数的方法叫做“筛法”。
其他常见的检测算法：费马素性检验，米勒拉宾测试 ，Solovay–Strassen测试，卢卡斯-莱默检验法。
主要方法：
主要方法就是查“质数表”法．编制质数表的过程是：按照自然数列，第一个数1不是质数，因此要除外，然后按顺序写出2至500的所有自然数，这些数中2是质数，把它留下，把2后面所有2的倍数划去，2后面的3是质数，接着再把3后面所有3的倍数划去，如此继续下去，剩下的便是500以内的全部质数。最早使用上述方法来寻求质数的人，是古代希腊数学家埃拉托斯特尼，由于他在开始时，先把自然数写在一块蜡板上，把不是质数的数（合数）分别刺上一个孔，这样，在蜡板上就被刺上了许多象筛子一样的孔，后来，大家就把这种寻求质数的方法叫做“筛法”。
这类的质数表还可以编制成数字范围更大一些的，如1000以内质数表等．判断一个自然数是不是质数，如在表所规定的数字范围内，即可用查表的方法进行判断。
素数：
质数(prime number)又称素数，有无限个。一个大于1的自然数，除了1和它本身外，不能被其他自然数整除，换句话说就是该数除了1和它本身以外不再有其他的因数;否则称为合数。
根据算术基本定理，每一个比1大的整数，要么本身是一个质数，要么可以写成一系列质数的乘积;而且如果不考虑这些质数在乘积中的顺序，那么写出来的形式是唯一的。最小的质数是2。
目前为止，人们未找到一个公式可求出所有质数。
假设给定一个自然数N，要求出N以内的所有素数，可以这样进行：因为N以内的自然数只有三种，一种是1，一种是合数，一种是素数；我们可以象筛东西那样，先把1筛掉，然后再把合数筛掉，剩下的就是素数了，这种在自然数列中寻找素数的方法就叫做埃拉托色尼筛法(简称埃氏筛法)。
用筛法找出不超过N的全部素数，可以遵循下面的定理进行。
辅助定理1：“如果n是不大于x的合数，那么n必有一个不大于√x的素约数(符号“√”表示开平方)”(证从略)。根据辅助定理1，我们只要用不大于√x的素数作筛子，就可将不大于X以内的所有的合数筛除掉。
虽然素数有无穷多个，但在自然数列中的一个相当长的数列中，却找不到一个素数，而有时会出现若p是素数，p+2也是素数的情况，所以素数的出现并无规则可言。
一个素数只有1和本身这两个约数，因此素数就不能再分解了。但是合数却有两个以上的素约数，那么合数能不能分解成约数全部是素数的乘积呢？答案是肯定的。
唯一分解定理：“任何大于1的自然数都可以分解成素数的乘积，如果不计较这些素因数的顺序，这种分解方法是唯一的”(证从略)。
根据唯一分解定理，欲求某自然数的倍数之数列，只要用该数乘以自然数列，即可得到该数的倍数之数列。由此可知，合数的出现是有规则可言的。埃氏筛法就是根据合数的出现是有规则可言的基础上，逐个地将不大于√x的素数的倍数筛掉。根据辅助定理1，可知，筛掉那些具有不大于√x素约数的合数，序列中已无合数的存在，剩下的就是大于√x至x的素数了。
在运用筛法时，就可发现，当筛除某数的倍数时，有时会遇到数列中的数已被前一个筛子所筛，这样就会造成计算上的误差。针对此种情况，在数论有一个逐步淘汰原则：
“设有N件事物，其中，N_i件有性质i，N_j件有性质j, ..., N_ij件兼有性质i及j，...，N_ijk件兼有性质i、j及k，...。则此事物中之既无性质i，又无性质j，又无性质k，...者之件数为
N-N_i-N_j-N_k-...+N_ij+...-N_ijk-...+...-...。”①。
根据埃氏筛法和逐步淘汰原则，数论创建了求不大于X以内的素数之函数π(x)。所谓的π(x)函数，是指：
π(x)=N-r-1-{r∑i=1}[N/pi]+{∑1≤ii*pj]-...
+(-1)r[N/pi*pj*...*pr]
这是数论中求自然数列中素数的个数问题之唯一的一个根据规律而创建的函数，而所谓的素数定理中的Lix(x)函数仅是由于计算出来的数值有接近于π(x)函数中的数值而被高斯先生提议替代π(x)函数之用。因为在π(x)函数中的取整之步骤，使得计算成为十分繁琐之事。但在Lix(x)函数中，并无所求素数的个数之任何规律，在Lix函数中，仅是对数函数的积分，而对数函数只是指数函数的反函数也。
参考资料：
只要是10000位以下的，我可以给你判断，马上出结果！
10000位，不是10000哦！本回答被提问者采纳
