MPRIME - Số nguyên tố ghép

Tác giả: flashmt

Ngôn ngữ: Pascal

const fi='';
      fo='';
      maxn=427999;
var d:array[2..maxn] of boolean;
    p:array[0..50000] of qword;
    pow:array[1..6] of qword;
    b:array[0..1] of longint;
    n,i:longint;
    kt:boolean;
    a:qword;

procedure prime;
var i,j,t:longint;
begin
     t:=trunc(sqrt(maxn));
     for i:=3 to t do
         if not d[i] then
         begin
              j:=i*i;
              while j<=maxn do
              begin
                   d[j]:=true;
                   j:=j+2*i;
              end;
         end;
     p[0]:=1; p[1]:=2;
     for i:=1 to maxn shr 1 do
         if not d[i shl 1+1] then
         begin
              inc(p[0]);
              p[p[0]]:=i shl 1+1;
         end;
end;

function check(a:qword):boolean;
var i:longint; k:qword;
begin
     check:=true;
     k:=trunc(sqrt(a));
     for i:=1 to p[0] do
         if p[i]>k then exit
         else
             if a mod p[i]=0 then
             begin
                  check:=false;
                  exit;
             end;
end;

function try(x:longint):boolean;
var s:string; i,j,l:longint;
begin
     try:=false;
     if (p[x]+p[x+1]) mod 3=0 then exit;
     str(p[x+1],s);
     l:=length(s);
     a:=p[x+1]+p[x]*pow[l];
     str(a,s);
     l:=length(s);
     b[1]:=0; b[0]:=0;
     for i:=1 to l do
         inc(b[i and 1],ord(s[i])-48);
     if abs(b[0]-b[1]) mod 11=0 then exit;
     try:=check(a);
end;

begin
     assign(input,fi); reset(input);
     assign(output,fo); rewrite(output);
     prime;
     pow[1]:=10;
     for i:=2 to 6 do pow[i]:=pow[i-1]*10;
     readln(n);
     i:=1;
     while n>0 do
     begin
          repeat
                kt:=try(i);
                i:=i+2;
                if kt then break;
          until false;
          dec(n);
     end;
     writeln(a);
     close(input); close(output);
end.

Download