Решето Эратосфена
Вполне вероятно, что алгоритм, придуманный более 2000 лет назад греческим математиком Эратосфеном Киренским, был первым в своем роде. Его задача – нахождение всех простых чисел до некоторого заданного числа n. Термин «решето» подразумевает фильтрацию, а именно фильтрацию всех чисел за исключением простых. Так, обработка алгоритмом числовой последовательности оставит лишь простые числа, все составные же отсеются.
Рассмотрим в общих чертах работу метода. Дана упорядоченная по возрастанию последовательность натуральных чисел. Следуя методу Эратосфена, возьмем некоторое число P изначально равное 2 – первому простому числу, и вычеркнем из последовательности все числа кратные P: 2P, 3P, 4P, …, iP (iP≤n). Далее, из получившегося списка в качестве P берется следующее за двойкой число – тройка, вычеркиваются все кратные ей числа (6, 9, 12, …). По такому принципу алгоритм продолжает выполняться для оставшейся части последовательности, отсеивая все составные числа в заданном диапазоне.
В приведенной таблице записаны натуральные числа от 2 до 100. Красным помечены те, которые удаляются в процессе выполнения алгоритма «Решето Эратосфена».
Программная реализация алгоритма Эратосфена потребует:
1. организовать логический массив и присвоить его элементам из диапазона от 2 до n логическую единицу;
2. в свободную переменную P записать число 2, являющееся первым простым числом;
3. исключить из массива все числа кратные P2, ступая с шагом по P;
4. записать в P следующее за ним не зачеркнутое число;
5. повторять действия, описанные в двух предыдущих пунктах, пока это возможно.
Обратите внимание: на третьем шаге мы исключаем числа, начиная сразу с P2, это связано с тем, что все составные числа меньшие P будут уже зачеркнуты. Поэтому процесс фильтрации следует остановить, когда P2 станет превышать n. Это важное замечание позволяет улучшить алгоритм, уменьшив число выполняемых операций.
Псевдокод алгоритма:
P←2
пока P2≤n выполнять
{
i←P2
если B[P]=true то
пока i≤n выполнять
{
B[i]←false
i←i+P
}
P←P+1
}
Он состоит из двух циклов: внешнего и внутреннего. Внешний цикл выполняется до тех пор, пока P2 не превысит n. Само же P изменяется с шагом P+1. Внутренний цикл выполняется лишь в том случае, если на очередном шаге внешнего цикла окажется, что элемент с индексом P не зачеркнут. Именно во внутреннем цикле происходит отсеивание всех составных чисел.
Код программы на C++:
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() //главная функция
{
int n;
cout<<"n > "; cin>>n;
bool *B=new bool[n];
Eratosthenes(B, n);
}
Код программы на Pascal:
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 {основной блок программы}
write('n > ');
read(n);
Eratosthenes(B, n);
end.
Решето Эратосфена для выявления всех простых чисел в заданной последовательности ограниченной некоторым n потребует O(n*log (log n)) операций. Поэтому уместнее использовать данный метод чем, например, наиболее тривиальный и затратный перебор делителей.