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.

Download