素数算法3种

末蓝、 2021-12-03 07:37 257阅读 0赞

①  
\--------------------------------------------------------------------------  
\--------------------------------------------------------------------------  
马宁德拉·阿格拉瓦  
（附：素数判定算法（当且仅当n为素数时，最终输出数才为素数））  
lnput： integer n>1  
1.if (n is of the form a^b, b>1)output COMPOSITE;  
2.R=2  
3.while (r<n) ｛  
4. if(ged(n,r)≠1) output COMPOSITE;  
5. if(r is prime)  
6. let q be the largest prime factor of r-1  
7. if(q≥4^r/2 logn)and (n(r-1)/q≠1(mod r))  
8. break;  
9. r←r+1;  
10. ｝  
11.for a=1 to 2r^1/2 logn  
12. if ((x-a)^n≠(x^n-a)(mod x^r-1,n))output COMPOSITE;  
13.output PRIME;

②  
\---------------------------------------------------------------------------  
\---------------------------------------------------------------------------  
数论学家利用费马小定理研究出了多种素数测试方法，目前最快的算法是拉宾米  
勒测试算法，其过程如下：  
（1）计算奇数M，使得N=(2\*\*r)\*M+1  
（2）选择随机数A<N  
（3）对于任意i<r，若A\*\*((2\*\*i)\*M) MOD N = N-1，则N通过随机数A的测试  
（4）或者，若A\*\*M MOD N = 1，则N通过随机数A的测试  
（5）让A取不同的值对N进行5次测试，若全部通过则判定N为素数  
若N 通过一次测试，则N 不是素数的概率为 25%，若N 通过t 次测试，则N 不是  
素数的概率为1/4\*\*t。事实上取t 为5 时，N 不是素数的概率为 1/128，N 为素数的  
概率已经大于99.99%。  
在实际应用中，可首先用300—500个小素数对N 进行测试，以提高拉宾米勒测试  
通过的概率，从而提高测试速度。而在生成随机素数时，选取的随机数最好让 r=0，  
则可省去步骤（3） 的测试，进一步提高测试速度

③  
\---------------------------------------------------------------------------  
\---------------------------------------------------------------------------

\#include <stdio.h>  
void main()  
\{  
long n,i;  
begin:  
cin>>n;  
for(i=2;i<n/2;i++)  
\{  
if(n%i==0)  
break;  
\}

if(i>=n/2)  
cout<<"n是素数";  
else  
cout<<"n不是素数";  
goto begin;

转载于:https://www.cnblogs.com/woodywu/archive/2009/07/06/2318324.html