Var n,p,k,i,j:integer; f:boolean; begin write('n = '); readln(n); p:=2; for i:=2 to n do begin f:=false; while not f do begin p:=p+1; k:=0; for j:=2 to round(sqrt(p)) do if p mod j = 0 then k:=k+1; f:=k=0; end; end; writeln(p); end.
Пример: n = 25 97
0 votes Thanks 0
fdgskm
Спасибо конечно, но у меня вся проблема в том, что ограничения до 1 миллиона, и этот код по времени не проходит на тесте, где вводится 1000000
petyaGavrikov
Да, если есть ограничение по времени, то этот вариант не подойдет. Нужно оптимизировать.
petyaGavrikov
Можно использовать решето Аткина. Для Вашей задачи подойдет. Очень быстро считает и до 1000000 и больше.
Answers & Comments
Verified answer
Var n,p,k,i,j:integer; f:boolean;begin
write('n = ');
readln(n);
p:=2;
for i:=2 to n do
begin
f:=false;
while not f do
begin
p:=p+1;
k:=0;
for j:=2 to round(sqrt(p)) do
if p mod j = 0 then k:=k+1;
f:=k=0;
end;
end;
writeln(p);
end.
Пример:
n = 25
97