PAGAIN - Prime Again
Tác giả: ll931110
Ngôn ngữ: Pascal
{$MODE DELPHI}
Program PAGAIN;
Const
input = '';
output = '';
a: array[1..3] of integer = (2,7,61);
Var
i,t: integer;
n: qword;
fi,fo: text;
Procedure openfile;
Begin
Assign(fi, input);
Reset(fi);
Assign(fo, output);
Rewrite(fo);
End;
Function power(x,p,k: qword): qword;
Var
u: qword;
Begin
If p = 0 then exit(1);
u:= power(x,p div 2,k);
If odd(p) then power:= ((u * u) mod k * x) mod k
else power:= (u * u) mod k;
End;
Function RabinMiller(k: qword): boolean;
Var
i,j: integer;
st,test,bs,p2: qword;
ch: boolean;
Begin
bs:= k - 1;
p2:= 0;
While bs mod 2 = 0 do
Begin
bs:= bs div 2;
inc(p2);
End;
RabinMiller:= false;
ch:= true;
For i:= 1 to 3 do if k >= a[i] then
Begin
ch:= false;
st:= power(a[i],bs,k);
test:= st;
If (test = 1) or (test = k - 1) then
Begin
ch:= true;
break;
End;
For j:= 1 to p2 - 1 do
Begin
test:= (test * test) mod k;
If (test = 1) or (test = k - 1) then
Begin
ch:= true;
break;
End;
End;
If not ch then exit(false);
End;
RabinMiller:= true;
End;
Procedure solve;
Var
k: qword;
Begin
Readln(fi, n);
If n = 3 then
Begin
writeln(fo, 2);
exit;
End;
k:= n;
dec(k);
If not odd(k) then dec(k);
While not RabinMiller(k) do k:= k - 2;
Writeln(fo, k);
End;
Procedure closefile;
Begin
Close(fo);
Close(fi);
End;
Begin
openfile;
Readln(fi, t);
For i:= 1 to t do solve;
closefile;
End.