MPRIME1 - Sum of Primes

Tác giả: ladpro98

Ngôn ngữ: Pascal

program mprime1;
uses    math;
const   fi='';
var     a:array[0..5000] of longint;
        sieve:array[1..11000] of boolean;
        d,res,i,n:longint;
        inp:text;
procedure initSieve;
var     i,j:longint;
begin
        i:=2;
        fillchar(sieve,sizeof(sieve),true);
        for i:=2 to 11000 do
        begin
                if not sieve[i] then continue;
                sieve[i]:=true;
                j:=i+i;
                while j<=11000 do
                begin
                        sieve[j]:=false;
                        inc(j,i);
                end;
        end;
end;

procedure InitA;
var     i,j:longint;
begin
        d:=0;
        for i:=2 to 11000 do
        begin
                if sieve[i] then
                begin
                        inc(d);
                        a[d]:=i;
                end;
        end;
        for i:=2 to d do
        a[i]:=a[i-1]+a[i];
end;

function find(last,key:longint):boolean;
var     l,r,m:longint;
begin
        l:=0;
        r:=last;
        while l<=r do
        begin
                m:=(l+r) div 2;
                if a[m]=key then exit(true);
                if a[m]<key then l:=m+1
                else r:=m-1;
        end;
        exit(false);
end;

begin
        initSieve;
        initA;
        assign(inp,fi);
        reset(inp);
        while not eof(inp) do
        begin
                readln(inp,n);
                if n=0 then break;
                res:=0;
                for i:=1 to d do
                if find(i-1,a[i]-n)
                then inc(res);
                writeln(res);
        end;
end.

Download