MPRIME1 - Sum of Primes
Tác giả: RR
Ngôn ngữ: Pascal
{$R+,Q+}
{$Mode objFPC}
uses math;
const
FINP='';
FOUT='';
MAXN=11000;
var
f1,f2:text;
p:array[0..2000] of longint;
count,sum:array[1..2000000] of longint;
sl,n,m:longint;
procedure openF;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
close(f1);
close(f2);
end;
function nt(n:longint):boolean; inline;
var
i,gh:longint;
begin
gh:=trunc(sqrt(n));
for i:=2 to gh do
if n mod i=0 then exit(false);
exit(true);
end;
procedure swap(var a,b:longint); inline;
var temp:longint;
begin temp:=a; a:=b; b:=temp; end;
procedure sort(l,r:longint); inline;
var
i,j,mid:longint;
begin
i:=l; j:=r; mid:=sum[l+random(r-l+1)];
repeat
while sum[i]<mid do inc(i);
while sum[j]>mid do dec(j);
if i<=j then
begin
swap(sum[i],sum[j]);
inc(i); dec(j);
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;
procedure init;
var
first,last,i,j:longint;
begin
for i:=2 to 11000 do
if nt(i) then
begin
inc(sl);
p[sl]:=i;
end;
for i:=2 to sl do
p[i]:=p[i-1]+p[i];
m:=0;
for first:=1 to sl do
for last:=first to sl do
begin
inc(m);
sum[m]:=p[last]-p[first-1];
end;
sort(1,m); j:=1; count[1]:=1;
for i:=2 to m do
if sum[i]>sum[j] then
begin
inc(j); sum[j]:=sum[i];
count[j]:=1;
end
else inc(count[j]);
m:=j;
end;
function get(key:longint):longint;
var
kq,l,r,mid:longint;
begin
kq:=0; l:=1; r:=m;
repeat
mid:=(l+r)>>1;
if sum[mid]<=key then
begin
kq:=mid;
l:=mid+1;
end
else r:=mid-1;
until l>r;
if sum[kq]<>key then exit(0)
else exit(count[kq]);
end;
begin
openF;
init;
read(f1,n);
while (n>0) do
begin
writeln(f2,get(n));
read(f1,n);
end;
closeF;
end.