begin read(n); for i := 2 to n do begin b := true; for j := 2 to i - 1 do if(i mod j = 0) then b := false; if(b) then write(i, ' '); end; end.
2)Решето Эратосфена
var ar: array of boolean; i, j, n, c: longint;
begin read(n); setlength(ar, n + 1); for i := 2 to n do ar[i] := true; for i := 2 to n do if(ar[i]) then begin write(i, ' '); c := i; j := i + c; while(j <= n) do begin ar[j] := false; j += c; end; end; end.
В приложении ниже программы выводящие зависимость времени работы программы от N. Из данных результатов можно сделать вывод: Алгоритм полного перебора делителей самый медленный и неэффективный, но простой в реализации, а решето Эратосфена работает намного быстрее перебора делителей, но сложнее в реализации и дает значительное преимущество только на довольно больших значениях N.
Answers & Comments
var
n, i, j: longint;
b: boolean;
begin
read(n);
for i := 2 to n do
begin
b := true;
for j := 2 to i - 1 do
if(i mod j = 0) then b := false;
if(b) then write(i, ' ');
end;
end.
2)Решето Эратосфена
var ar: array of boolean;
i, j, n, c: longint;
begin
read(n);
setlength(ar, n + 1);
for i := 2 to n do
ar[i] := true;
for i := 2 to n do
if(ar[i]) then
begin
write(i, ' ');
c := i;
j := i + c;
while(j <= n) do
begin
ar[j] := false;
j += c;
end;
end;
end.
В приложении ниже программы выводящие зависимость времени работы программы от N.
Из данных результатов можно сделать вывод: Алгоритм полного перебора делителей самый медленный и неэффективный, но простой в реализации, а решето Эратосфена работает намного быстрее перебора делителей, но сложнее в реализации и дает значительное преимущество только на довольно больших значениях N.