求pascal判断素数的米勒拉宾算法判断一个数是否为素数注意,一定要是米勒拉宾算法,暴力试除法就不用了,
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/04 00:47:38
![求pascal判断素数的米勒拉宾算法判断一个数是否为素数注意,一定要是米勒拉宾算法,暴力试除法就不用了,](/uploads/image/z/3925978-34-8.jpg?t=%E6%B1%82pascal%E5%88%A4%E6%96%AD%E7%B4%A0%E6%95%B0%E7%9A%84%E7%B1%B3%E5%8B%92%E6%8B%89%E5%AE%BE%E7%AE%97%E6%B3%95%E5%88%A4%E6%96%AD%E4%B8%80%E4%B8%AA%E6%95%B0%E6%98%AF%E5%90%A6%E4%B8%BA%E7%B4%A0%E6%95%B0%E6%B3%A8%E6%84%8F%2C%E4%B8%80%E5%AE%9A%E8%A6%81%E6%98%AF%E7%B1%B3%E5%8B%92%E6%8B%89%E5%AE%BE%E7%AE%97%E6%B3%95%2C%E6%9A%B4%E5%8A%9B%E8%AF%95%E9%99%A4%E6%B3%95%E5%B0%B1%E4%B8%8D%E7%94%A8%E4%BA%86%2C)
求pascal判断素数的米勒拉宾算法判断一个数是否为素数注意,一定要是米勒拉宾算法,暴力试除法就不用了,
求pascal判断素数的米勒拉宾算法
判断一个数是否为素数
注意,一定要是米勒拉宾算法,暴力试除法就不用了,
求pascal判断素数的米勒拉宾算法判断一个数是否为素数注意,一定要是米勒拉宾算法,暴力试除法就不用了,
Miller-Rabin算法是基于费马定理的:
如果n为质数,(a,n)=1 那么 a^(n-1)=1 (mod n)
Miller-Rabin算法就是费马定理反向的使用:
如果有足够多的a,(a,n)=1 使a^(n-1)=1 (mod n)都成立
那么n为质数
但是并不是一个完美的算法,
如果以2,3,5,7为底,在2.5*10^13以内只有3215031751这一个数是判断错误的
因为A^B可以在logB的时间复杂度内运算完
所以Miller-Rabin算法的复杂度O(logn)比起朴素O(sqrt(n))快上了非常多
程序:(你可以让p数组随机,不一定要用2,3,5,7为底)
const
p:array[1..4] of integer=(2,3,5,7);
var
n,i:longint;
f:boolean;
function exp(a,b:longint):longint; //计算a^b除以n的余数
var
t:qword;
begin
if b=0 then exit(1);
if b=1 then exit(a mod n);
t:=sqr(exp(a,b div 2)) mod n;
if b mod 2=1 then t:=t*a mod n;
end;
begin
readln(n);
f:=true;
for i:=1 to 4 do
if exp(p[i],n-1)1 then
begin
f:=false;
break;
end;
if f then writeln('YES') else writeln('NO');
end.
其中,需要自行判断n为1,2,3,5,7的情况(一开始加个if就行)
这个程序能处理出longint内所有>7的素数