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.

Download