Question

100балов. решите второе задание пожалуйста.
через паскаль или кумир.

Answer 1

1)Полный перебор всех делителей

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.

2dbda8f33b0d3c35224f6af8c705526f.pas

f42c4b909d67e783f39f74b1b37e4173.pas