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

Материал из Википедии — свободной энциклопедии

Решето́ Эратосфе́на — простой алгоритм нахождения всех простых чисел до некоторого целого числа n. Он был создан древнегреческим математиком Эратосфеном.

[править] Пример для n = 20

Запишем натуральные числа начиная от 2 до 20 в ряд:

  2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20

Первое число в списке 2 — простое. Пройдём по ряду чисел, вычёркивая все числа кратные 2 (каждое второе, начиная с 2² = 4):

  2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20 

Следующее невычеркнутое число 3 — простое. Пройдём по ряду чисел, вычёркивая все числа кратные 3 (каждое третье, начиная с 3² = 9):

  2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20 

Следующее невычеркнутое число 5 — простое. Пройдём по ряду чисел, вычёркивая все числа кратные 5 (каждое пятое, начиная с 5² = 25). И т. д.

Необходимо провести вычёркивания кратных для всех простых чисел p, для которых . В результате все составные числа будут вычеркнуты, а невычеркнутыми останутся все простые числа. Для n = 20 уже после вычёркивания кратных числу 3 все составные числа получаются вычеркнутыми.

[править] См. также

• Решето Сундарама
• Корекурсия
• Решето Аткина

[править] Примеры реализации

[править] Turbo Pascal

prost:=1; //Подготовка параметра для нахождения простых чисел
for i:=1 to n do //Цикл движения по массиву чисел
begin //НАЧАЛО
if p[i]=0 then continue else//Чтоб лишний раз не заходить в цикл
 inc(prost);                //Увеличение параметра,
 j:=i;                      //Подготовка параметра вложенного цикла
 while j<=n do              //Вложенный цикл для определения простых чисел
  if (p[j] mod prost=0)     //Если остаток от деления элемента на следующее простое число равен 0..
     and(p[j]<>0)           //..и этот элемент не равен 0..
     and(p[j]>prost) then   //..и этот элемент больше параметра prost..
  begin p[j]:=0; inc(j); end //..это СОСТАВНОЕ число, удаляем его из массива и ищем далее
  else inc(j);               //иначе это простое число, и дальнейший поиск
end; //КОНЕЦ