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

Вполне вероятно, что алгоритм, придуманный более 2000 лет назад греческим математиком Эратосфеном Киренским, был первым в своем роде. Его единственная задача – нахождение всех простых чисел до некоторого заданного числа N. Термин «решето» подразумевает фильтрацию, а именно фильтрацию всех чисел за исключением простых. Так, обработка алгоритмом числовой последовательности оставит лишь простые числа, все составные же отсеются.

Рассмотрим в общих чертах работу метода. Дана упорядоченная по возрастанию последовательность натуральных чисел. Следуя методу Эратосфена, возьмем некоторое число P изначально равное 2 – первому простому числу, и вычеркнем из последовательности все числа кратные P: 2P, 3P, 4P, …, iP (iP≤N). Далее, из получившегося списка в качестве P берется следующее за двойкой число – тройка, вычеркиваются все кратные ей числа (6, 9, 12, …). По такому принципу алгоритм продолжает выполняться для оставшейся части последовательности, отсеивая все составные числа в заданном диапазоне.

В приведенной таблице записаны натуральные числа от 2 до 100. Красным помечены те, которые удаляются в процессе выполнения алгоритма «Решето Эратосфена».

Программная реализация алгоритма Эратосфена потребует:

1. организовать логический массив и присвоить его элементам из диапазона от 2 до N логическую единицу;
2. в свободную переменную P записать число 2, являющееся первым простым числом;
3. исключить из массива все числа кратные P², ступая с шагом по P;
4. записать в P следующее за ним не зачеркнутое число;
5. повторять действия, описанные в двух предыдущих пунктах, пока это возможно.

Обратите внимание: на третьем шаге мы исключаем числа, начиная сразу с P², это связано с тем, что все составные числа меньшие P будут уже зачеркнуты. Поэтому процесс фильтрации следует остановить, когда P² станет превышать N. Это важное замечание позволяет улучшить алгоритм, уменьшив число выполняемых операций.

Так будет выглядеть псевдокод алгоритма:

Он состоит из двух циклов: внешнего и внутреннего. Внешний цикл выполняется до тех пор, пока P² не превысит N. Само же P изменяется с шагом P+1. Внутренний цикл выполняется лишь в том случае, если на очередном шаге внешнего цикла окажется, что элемент с индексом P не зачеркнут. Именно во внутреннем цикле происходит отсеивание всех составных чисел.

Код программы на C++:

#include "stdafx.h"
#include <iostream>
using namespace std;
//решето Эратосфена
void Eratosthenes(bool B[], int N)
{
int i, P;
for (P=2; P<=N; P++) B[P]=true;
P=2;
while (P*P<=N)
{
i=P*P;
if (B[P])
while (i<=N)
{
B[i]=false;
i=i+P;
}
P=P+1;
}
cout<<"Простые числа: ";
for (P=2; P<=N; P++)
if (B[P]==true) cout<<" "<<P;
}
//главная функция
void main()
{
setlocale(LC_ALL,"Rus");
int N;
cout<<"N > "; cin>>N;
bool *B=new bool[N];
Eratosthenes(B, N);
system("pause>>void");
}

Код программы на Pascal:

program EratosthenesAlg;
uses crt;
type Arr=array[1..1000] of boolean;
var
N, i, P: integer;
B: Arr;
{решето Эратосфена}
procedure Eratosthenes(B: Arr; N: integer);
begin
for P:=2 to N do B[P]:=true;
P:=2;
while (P*P<=N) do
begin
i:=P*P;
if B[P] then
while i<=N do
begin
B[i]:=false;
i:=i+P;
end;
P:=P+1;
end;
write('Простые числа: ');
for P:=2 to n do
if B[P]=true then write(P, ' ');
end;
{основной блок программы}
begin
clrscr;
write('N > '); read(N);
Eratosthenes(B, N);
end.

Решето Эратосфена для выявления всех простых чисел в заданной последовательности ограниченной некоторым N потребует O(Nlog (log N)) операций. Поэтому уместнее использовать данный метод чем, например, наиболее тривиальный и затратный перебор делителей.