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.

Download