一定要注意细节问题,不要在数据的最后加上空格或者空行。
RQNOJ ---> RenQing
var ans:array[0..10000]of longint;
nzz:array[0..30000]of boolean;
f,g,from,orz:array[0..30000]of longint;
n,i,m,j,my:longint;
begin
assign(input,’qq.in’);assign(output,’qq.out’);
reset(input);rewrite(output);
readln(n);
m:=0;
for i:=1 to n do
begin
readln(ans[i]);
if ans[i]>m then m:=ans[i];
end;
nzz[1]:=true;
for i:=2 to trunc(sqrt(m)) do
for j:=2 to m div i do nzz[i*j]:=true;
for i:=1 to m do if not nzz[i] then write(i,’ ’);
j:=0;
for i:=2 to m do
begin
if not nzz[i] then
begin
inc(j);
orz[j]:=i;
from[i]:=j;
end
else
from[i]:=j;
end;
f[1]:=-1;g[1]:=0; {f1=-1}
for i:=2 to m do
begin
if (not nzz[i]) or (not nzz[i-1]) then
begin
f[i]:=1;
continue;
end;
my:=123456789;
for j:=1 to from[i] do if (f[i-orz[j]]=-1) and (my>g[i-orz[j]]) then my:=g[i-orz[j]];
if my<>123456789 then f[i]:=my+1
else
begin
f[i]:=-1;
my:=-2;
for j:=1 to from[i] do
if (f[i-orz[j]]<>-1) and (my<f[i-orz[j]]) then my:=f[i-orz[j]];
f[i]:=my+1;
end;
end;
for i:=1 to n do writeln(f[ans[i]]);
close(input);close(output);
end.