PAGAIN - Prime Again
Tác giả: RR
Ngôn ngữ: Pascal
{$R+,Q+}
{$Mode objFPC}
const
FINP = '';
FOUT = '';
k = 2;
var
f1,f2 : text;
n : qword;
test : longint;
procedure openF;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
close(f1);
close(f2);
end;
//Miller-rabin test by Pham Quang Vu
//power = (a^q) mod n
function power(a,q,n:qword):qword; inline;
var
u:qword;
begin
if q=1 then exit(a mod n);
if q=0 then exit(1);
u:=power(a,q shr 1,n);
if q and 1=1 then exit( ((u*u) mod n*a) mod n )
else exit( (u*u) mod n );
end;
function millertest(n,a,q,t:qword):boolean; inline;
var
pre,c:qword;
i:longint;
begin
c:=power(a,q,n);
pre:=n-1;
for i:=0 to t do
begin
if c=1 then exit(pre=n-1);
pre:=c;
c:=(c*c) mod n;
end;
exit(false);
end;
//n = 2^t * q
procedure cal(n:qword; var q,t:qword); inline;
begin
t:=0;
while n and 1=0 do
begin
inc(t);
n:=n shr 1;
end;
q:=n;
end;
function prime(n:qword):boolean; inline;
var
i:longint;
a,q,t:qword;
begin
cal(n-1,q,t);
for i:=1 to k do
begin
a:=random(n-1)+1;
if not millertest(n,a,q,t) then exit(false);
end;
exit(true);
end;
//End of Miller-rabin test by Pham Quang Vu
procedure solve;
begin
n-=1;
if n and 1=0 then n-=1;
repeat
if (n=3) or (n=5) or (n=7) then
begin
writeln(f2,n);
exit;
end;
if (n mod 5>0) and (n mod 7>0) then
if (n mod 3>0) and prime(n) then
begin
writeln(f2,n);
exit;
end;
n-=2;
until false;
end;
begin
openF;
readln(f1,test);
for test:=1 to test do
begin
readln(f1,n);
if n=3 then writeln(f2,2)
else solve;
end;
closeF;
end.