CPRIME - Prime Number Theorem

Tác giả: ll931110

Ngôn ngữ: Pascal

{$MODE DELPHI}
Program CPRIME2;
Const
  input  = '';
  output = '';
  maxn = 50000000;
Var
  fi,fo: text;
  a: array[1..maxn] of boolean;
  p: array[1..6000000] of integer;
  num: integer;

Procedure openfile;
Begin
  Assign(fi, input);
    Reset(fi);

  Assign(fo, output);
    Rewrite(fo);
End;

Procedure gens;
Var
  i,k,t: integer;
Begin
  num:= 1;
  p[1]:= 2;

  Fillchar(a, sizeof(a), true);
  For i:= 1 to maxn do if a[i] then
    Begin
      t:= 2 * i + 1;
      inc(num);
      p[num]:= t;

      k:= i;
      While k <= maxn do
        Begin
          k:= k + t;
          If k <= maxn then a[k]:= false;
        End;
    End;
End;

Function search(x: integer): integer;
Var
  inf,sup,med,r: integer;
Begin
  inf:= 1;
  sup:= num;

  r:= 0;
  Repeat
    med:= (inf + sup) shr 1;
    If x = p[med] then exit(med);
    If x > p[med] then
      Begin
        r:= med;
        inf:= med + 1;
      End
    else sup:= med - 1;
  Until inf > sup;

  search:= r;
End;

Procedure solve;
Var
  t,x: integer;
  val: real;
Begin
  Repeat
    Readln(fi, x);
    If x = 0 then break;

    t:= search(x);
    val:= abs((t - x /ln(x))) / t * 100;
    Writeln(fo, val:0:1);
  Until x = 0;
End;

Procedure closefile;
Begin
  Close(fo);
  Close(fi);
End;

Begin
  openfile;
  gens;
  solve;
  closefile;
End.

Download