费马小定理 pascal
来源:学生作业帮 编辑:作业帮 分类:综合作业 时间:2024/05/11 19:24:30
费马小定理 pascal
用费马小定理判素数.其他的不需要
用费马小定理判素数.其他的不需要
var n:longint;
function modular_exp(a,p,k:longint):int64;
var t,ans:int64;
begin
t:=a mod k; ans:=1;
while p>0 do
begin
if (p and 1=1) then ans:=(ans*t) mod k;
t:=(t*t) mod k;
p:=p shr 1;
end;
modular_exp:=ans;
end;
function miller_rabbin(n:longint):boolean;
var i,k,epsilon:longint;
begin
epsilon:=round(exp(1)*ln(n)/ln(2));
for i:=1 to epsilon do
begin
k:=random(n-1)+1;
if modular_exp(k,n-1,n)<>1 then exit(false);
end;
exit(true);
end;
begin
readln(n);
if miller_rabbin(n) then
writeln(n,' is a prime.')
else writeln(n,' is not a prime.');
end.
这个程序要在Free Pascal环境下运行.
function modular_exp(a,p,k:longint):int64;
var t,ans:int64;
begin
t:=a mod k; ans:=1;
while p>0 do
begin
if (p and 1=1) then ans:=(ans*t) mod k;
t:=(t*t) mod k;
p:=p shr 1;
end;
modular_exp:=ans;
end;
function miller_rabbin(n:longint):boolean;
var i,k,epsilon:longint;
begin
epsilon:=round(exp(1)*ln(n)/ln(2));
for i:=1 to epsilon do
begin
k:=random(n-1)+1;
if modular_exp(k,n-1,n)<>1 then exit(false);
end;
exit(true);
end;
begin
readln(n);
if miller_rabbin(n) then
writeln(n,' is a prime.')
else writeln(n,' is not a prime.');
end.
这个程序要在Free Pascal环境下运行.