16811 2002-11-15 12:00:48 BigGuava
116 .PAS Accepted 63 ms 52 kb
var
i,j,k,m,n:integer;
prime: array[1..1300] of word;
p:array[1..210] of word;
c:array[0..10000] of word;
from:array[0..10000] of word;
ok:boolean;
begin
{$IFNDEF ONLINE_JUDGE}
assign(input,'i116.txt'); reset(input);
assign(output,'o116.txt'); rewrite(output);
{$ENDIF}
prime[1]:=2; k:=1;
i:=3;
while i<10000 do begin
m:=trunc(sqrt(i)); ok:=true;
for j:=1 to k do begin
if i mod prime[j]=0 then begin
ok:=false;
break;
end;
if prime[j]>m then break;
end;
if ok then begin
inc(k);
prime[k]:=i;
end;
inc(i,2);
end;
for i:=1 to 1000 do
if prime[i]>k then break
else p[i]:=prime[prime[i]];
//201 numbers
fillchar(c,sizeof(c),255);
c[0]:=0;
for i:=0 to 10000 do if c[0]<>65535 then
for j:=1 to 201 do begin
if p[j]+i>10000 then break;
if c[p[j]+i]>c[i]+1 then begin
c[p[j]+i]:=c[i]+1;
from[p[j]+i]:=i;
end;
end;
readln(n);
if c[n]=65535 then begin
writeln(0);
end else begin
i:=from[n]; j:=1;
while i<>0 do begin
p[j]:=n-i;
inc(j);
n:=i;
i:=from[i];
end;
p[j]:=n;
for i:=1 to j-1 do for k:=i+1 to j do if p[i]<p[k] then begin
n:=p[i]; p[i]:=p[k]; p[k]:=n;
end;
writeln(j);
for i:=1 to j do write(p[i],' ');
end;
end.