PAGAIN - Prime Again
Tác giả: ladpro98
Ngôn ngữ: Pascal
const fi='';
function powmod(i,j,k:longword):qword;
var t:qword;
begin
if j=1 then exit(i mod k);
t:=powmod(i,j div 2,k) mod k;
if odd(j) then
exit((((t*i) mod k)*t) mod k);
exit((t*t) mod k);
end;
function rabinmiller(p:longword):boolean;
var temp,s,a:int64;
modul:qword;
i:longint;
begin
if (p<2) then exit(false);
if (p <> 2) and (p mod 2 = 0) then exit(false);
s:=p-1;
while s mod 2 = 0 do s:=s div 2;
for i:=1 to 3 do
begin
a:=random(p-3)+2;
temp:=s;
modul:=powmod(a,temp,p);
while (temp<>p-1) and (modul<>1) and (modul<>p-1) do
begin
modul:=((modul mod p)*(modul mod p)) mod p;
temp:=temp*2;
end;
if (modul<>p-1) and (temp mod 2 = 0) then exit(false);
end;
exit(true);
end;
procedure input;
var i,t:longint;
j:int64;
inp:text;
begin
randomize;
assign(inp,fi);
reset(inp);
readln(inp,t);
for i:=1 to t do
begin
readln(inp,j);
dec(j);
while j>=2 do
begin
if rabinmiller(j) then
begin
writeln(j);
break;
end;
dec(j);
end;
end;
close(inp);
end;
begin
input;
end.