В этой публикации решим следующую задачу:
Вывести все простые числа из некоторого диапазона с использованием алгоритма "Решето Эратосфена".
Простое число - это натуральное число, имеющее ровно 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
Комментариев нет:
Отправить комментарий