CPRIME - Prime Number Theorem
Tác giả: khuc_tuan
Ngôn ngữ: Pascal
// {$APPTYPE CONSOLE}
{$mode delphi}
uses math, sysutils;
const
max = 100000000;
max2 = 10000;
var
ip : array[0..max] of boolean;
p : array[0..6000000] of integer;
le, ri, mi, np : integer;
n, x, y, x2, y2 : integer;
begin
ip[2] := true;
ip[3] := true;
for x := 1 to max2 do
begin
x2 := x * x;
for y := 1 to max2 do
begin
y2 := y * y;
n := 4 * x2 + y2;
if (n <= max) and ((n mod 12 = 1) or (n mod 12 = 5)) then
ip[n] := not ip[n];
dec(n, x2);
if (n <= max ) and (n mod 12 = 7) then
ip[n] := not ip[n];
dec(n, y2); dec(n, y2);
if (x>y) and (n<=max) and (n mod 12 = 11) then
ip[n] := not ip[n];
end;
end;
for n:=5 to max2 do
if ip[n] then
begin
x := n * n;
y := x;
while y <= max do
begin
ip[y] := false;
inc( y, x);
end;
end;
np := 0;
for n:=2 to max do
if ip[n] then
begin
inc(np);
p[np] := n;
end;
// writeln(np);
while true do
begin
read(x);
if x=0 then break;
le := 1;
ri := np;
while le < ri do
begin
mi := (le+ri) div 2 + 1;
if p[mi] > x then ri := mi - 1
else le := mi;
end;
writeln( (abs(le - x / ln(x)) / le * 100) :0 :1);
end;
end.