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.

Download