作业帮Miller-Rabbin素数测试法求一个用Miller-Rabbin算法判断是否为素数的程序,注意要用PascalPascal!Pascal!Pascal!Pascal!Pascal!Pascal!Pascal!Pascal!最好有说明
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/02 07:20:53
Miller-Rabbin素数测试法求一个用Miller-Rabbin算法判断是否为素数的程序,注意要用PascalPascal!Pascal!Pascal!Pascal!Pascal!Pascal!Pascal!Pascal!最好有说明
Miller-Rabbin素数测试法
求一个用Miller-Rabbin算法判断是否为素数的程序,注意要用Pascal
Pascal!Pascal!Pascal!Pascal!Pascal!Pascal!Pascal!Pascal!
最好有说明
Miller-Rabbin素数测试法求一个用Miller-Rabbin算法判断是否为素数的程序,注意要用PascalPascal!Pascal!Pascal!Pascal!Pascal!Pascal!Pascal!Pascal!最好有说明
如果说明的话.
额
就是利用费马小定理：当 p 为 质数的时候 ,a^(p-1) mod p = 1
其中 a,p 要互质
那么 Miller-Rabbin 算法就是说
如果 a^ (p-1) mod p = 1 那么 p 很有可能是质数 (大约75%的概率)
如果 a^ (p-1) mod p 1 那么 p 一定 不是质数
如果你对每个p 拿 count=30 个数去检验
那么出错的概率为 (0.25)^count 是很小很小的数字
所以 Miller-Rabbin 算法是很有效的求质数的方法
（别的算法要么 O(n) 要么 O(sqrt(n)),这个算法是 O（count*log(n)） 的
其中count 是一个常数）
program cly;
const
inf='prime1.in'; ouf='prime1.out'; count=30;
limit=1000000;
var
task,a,b,ran,i,qw:longint;
pct:array[1..limit]of boolean;
procedure prepare;
var
i,j:longint;
begin
fillchar(pct,sizeof(pct),true);
i:=2;
while i