①
--------------------------------------------------------------------------
--------------------------------------------------------------------------
马宁德拉·阿格拉瓦
（附：素数判定算法（当且仅当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;
}