判断100位的整数为素数的算法

Miller-Rabbin素数测试法

这个一般是要借助于计算机的，网上有很多这样的程序，如果靠手算的话，确实没有简单的方法。

与1到根号这个数+1相除，都不能整除就为素数

除以6余1

素数算法
素数判定算法（印度理工学院计算机科学与工程学系的科学家马宁德拉·阿格拉瓦和他的两位在校本科生尼拉叶·卡雅尔和尼汀·萨克斯特纳）

（当且仅当n为素数时，最终输出数才为素数）

Input： integer n>l
1. (n is of the form ab，b>1) output COMPOSITE;
2. r=2;
3. while(r
4. if(gcd(n，r)≠1) output COMPOSITE；
5. if(r is prime)
6. let q be the largest prime factor of r-1;
7. if(q ≥) and (n ?1(mod r))
8. break；
9. r←r+1;
10. }
11.for a=1 to logn
12. if((x-a)n?(xn-a)(mod xr1,n)) output COMPOSITE;
13.output PRIME;
判定素数的确定性多项式算法(同上)
有朋友发EMAIL问到这个算法,现在我把算法公布出来.论文可以参考2002年,印度,Agrawal等人论文的"primes is in P".
s1: r=2
s2: 当r<n,转s3;
s3: 若gcd(n,r)<>1,则判定n为合数;
s4: 若r是素数,q是r-1的最大素数因子,若(q>=4sqrt(r)log(n)^(power(n,r-1/q)<>1 mod r),则转s6,否则转s5;
s5: r=r+1
s6: 对1<