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.

Download