Решето Эратосфена на языке Паскаль (поиск простых чисел быстро)

В этой публикации решим следующую задачу:

Вывести все простые числа из некоторого диапазона с использованием алгоритма "Решето Эратосфена".

Простое число - это натуральное число, имеющее ровно 2 делителя: 1 и само число. Например, 2, 3, 5, 7, 11.

Для быстрого поиска простых чисел будем использовать алгоритм "Решето Эратосфена", заключающийся в просеивании последовательности чисел так, что составные числа последовательности вычеркиваются.

Идея алгоритма

В упорядоченной последовательности натуральных чисел возьмем число k, равное 2 – первому простому числу, и вычеркнем из последовательности все числа, кратные k: 2k, 3k, 4k, …, ik (ik≤N). Далее, в качестве k возьмем следующее за 2 число – это 3, и вычеркнем все кратные 3 числа (6, 9, 12, …).

Слово "вычеркнем" следует понимать так: сделаем число нулем.

Как будем решать задачу

Последовательность натуральных чисел сохраним в массиве. Номера ячеек отождествим с числами. Ячейки с номерами 0 и 1 должны быть равны 0 (0 и 1 не являются простыми числами).

Внешний цикл запустим по k от 2 до N.

Если ячейка a[k] хранит число, не равное 0, то возьмем j=k и во внутреннем цикле пока j<=N-k, с шагом j=j+k, будем обнулять ячейку a[j].

Приведем код программы на языке Паскаль 

var a:array of integer;

    k,j,n:integer;

begin

  {простые числа до 500}

  n:=500;

  setlength(a,n+1);

  for k:=0 to n do a[k]:=k;

  a[1]:=0;

  for k:=2 to n do

  begin

    if a[k]<>0 then  

      begin 

       j:=k;

       while (j<=n-k) do

        begin

         j:=j+k;

         a[j]:=0;

        end;

      end;

  end;

  a.Where(k->k<>0).print; {вывод элементов массива, не равных 0}

end.

Время выполнения программы

Сравним время выполнения программ для поиска простых чисел в диапазоне от 0 до 50 000 с использованием алгоритма "Решето Эратосфена" и алгоритма, в котором для каждого числа считается количество его делителей.

Решето Эратосфена

Подсчет количества делителей

var a:array of integer;     k,j,n:integer; begin   var d := Milliseconds;   {простые числа до 50000}   n:=50000;   setlength(a,n+1);   for k:=0 to n do a[k]:=k;   a[1]:=0;   for k:=2 to n do   begin     if a[k]<>0 then         begin         j:=k;        while (j<=n-k) do         begin          j:=j+k;          a[j]:=0;         end;       end;    end;  // a.Where(k->k<>0).print;   println;   println((Milliseconds-d)/1000); end. Время: 0.041 с

var a:array of integer;     k,j,n,p:integer; begin   var d := Milliseconds;   {простые числа до 50000}   n:=50000;   setlength(a,n+1);   for k:=0 to n do a[k]:=0;   a[1]:=0;   for k:=2 to n do   begin     p:=0;     for j:=1 to k div 2 do       if k mod j=0 then p+=1;     if p=1 then a[k]:=k;   end;   //a.Where(k->k<>0).print;   println;   println((Milliseconds-d)/1000); end. Время: 10.894 с

Очевидно, что программа "Решето Эратосфена" ищет простые числа быстрее.

Для промежутка чисел [0; 100 000] время выполнения программы составило 0.096 с; программа, подсчитывающая количество делителей, выполнилась за 46.2 с.

Уменьшить время выполнения программы, подсчитывающей количество делителей, можно за счет поиска сразу двух делителей, идя в цикле до корня квадратного от числа k. 

Таблица простых чисел до 200