prime.pas

质性测试

{Input a n,Output the min prime bigger than n}
const max=1 shl 16;{max sqrt of n}
var f,g:text;
    p:array[1..max div 4]of dword;
    a:array[1..max]of 0..1;
    i,j,l,n:dword;
function isprime(n:dword):boolean;
 var i,t:dword;
  begin
   t:=0;i:=1;
   while(t=0)and(p[i]*p[i]<=n)do 
    begin
     if n mod p[i]=0 then t:=1;
     inc(i);
    end;
   if t=1 then isprime:=false else isprime:=true;
  end;
begin
 assign(f,'prime.in');
 assign(g,'prime.out');
 reset(f);
 rewrite(g);
 read(f,n);
 close(f);
 fillchar(a,sizeof(a),0);
 {0:is prime 1:not a prime}
 a[1]:=1;i:=2;
 while i*i<=max do 
  begin
   for j:=i to(max div i)do a[i*j]:=1;
   inc(i);
   while(i<=max)and(a[i]=1)do inc(i);
  end;
 l:=0;
 for i:=1 to max do 
  if a[i]=0 then 
   begin
    inc(l);
    p[l]:=i;
   end;
 repeat
  inc(n);
 until isprime(n);
 writeln(g,n);
 close(g);
end.