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

Решето́ Ератосфе́на в математиці — алгоритм пошуку всіх простих чисел, менших заданого цілого числа ${\displaystyle N}$, створений давньогрецьким математиком Ератосфеном.

Якщо потрібно знайти всі прості числа менші за певне число N, виписуються всі числа від 2 до N.

1. Перше просте число — два. Викреслимо всі числа більші двох, які діляться на два (4, 6, 8 …).
2. Наступне число, яке залишилося незакресленим (три), є простим. Викреслюємо всі числа більші трьох та кратні трьом (6, 9 …).
3. Наступне незакреслене число (п'ять) є простим. Викреслимо всі числа більші п'яти та кратні п'яти (10, 15, 20, 25 …).
4. Повторюємо операцію поки не буде досягнуто число N:
   • Наступне незакреслене число є простим. Викреслимо всі числа більші нього та кратні йому.

Числа, які залишилися незакресленими після цієї процедури — прості^[1].

Викреслювати кратні для кожного простого p можна розпочинаючи з p², а не з 2p^[2]. Тобто:

• кратні трьом викреслюють починаючи з 3²=9 (оскільки 6 уже викреслено як кратне двом);
• кратні п'яти викреслюють починаючи з 25=5² (числа 10, 15, 20 уже викреслено, бо вони кратні двом або трьом);
• кратні семи починають викреслювати з 49, оскільки 14, 21, 28, 35 і 42 вже викреслено як кратні двом, трьом чи п'яти;
• і т.д.

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

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

Перше число в рядку 2 — просте. Викреслимо всі числа кратні 2 (кожне друге, починаючи з ${\displaystyle 2^{2}=4}$):

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

Наступне незакреслене число 3 — просте. Викреслимо всі числа кратні 3 (кожне третє, починаючи з ${\displaystyle 3^{2}=9}$):

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

Наступне незакреслене число 5 — просте. Викреслимо всі числа кратні 5 (кожне п'яте, починаючи з ${\displaystyle 5^{2}=25}$). І т. д.

Необхідно викреслити кратні для всіх простих чисел ${\displaystyle p}$, для яких ${\displaystyle p^{2}\leq n}$. В результаті всі складені числа будуть викреслені, а залишаться всі прості числа. Для ${\displaystyle n=20}$ вже після викреслювання кратних числу 3 всі складені числа виявляються викресленими.

Решето Ератосфена може бути виражене в псевдокоді наступним чином^[3][2]:

Алгоритм Решето Ератосфена є
  вхід : ціле число n > 1.
  вихід : всі прості числа від 2 до n.

  нехай A — масив булевих значень, індексованих цілим числом s від 2 до n,
  ініціалізуємо весь масив значеннями true.
  
  для i = 2, 3, 4, ..., що не перевищує √n робити
    якщо А [i] є true
      для j = i2, i2 + i, i2 + 2i, i2 + 3i, ..., що не перевищує n робити
                A[j] := false

  повернути всі i де A[i] є true.

Цей алгоритм видає всі прості числа, що не перевищують n . Він включає загальну оптимізацію, яка полягає в тому, щоб почати перераховувати числа кратні кожному простому i з i². Часова складність цього алгоритму становить O(n log log n)^[2], при стандартному припущенні, що оновлення масиву відбувається за час O(1).

Реалізація мовою Python:

import math
N = 1000000  # діапазон в якому шукаємо прості числа
prime = [True] * N
prime[0], prime[1] = False, False # 0 та 1 не є простими
for i in range(2, math.ceil(math.sqrt(N))):  # від 2 до квадратного кореня з N 
    if prime[i]:  # якщо просте видаляємо всі числа кратні до нього
        j = i * i   # для i=2,j будуть такі значення 4,6,8,10,12... для i=3 j — 9,12,15,18,21...
        while j < N:
            prime[j] = False
            j += i

Алгоритм потребує ${\displaystyle O(N)}$ біт пам'яті та ${\displaystyle O(N\log \log N)}$ математичних операцій.

Попри свою простоту, алгоритм є вельми ефективним. Лише у другій половині XX-го сторіччя, із розвитком комп'ютерної техніки та програмування було винайдено асимптотично кращі методи. Однак, вони складніші й їх перевага виявляється лише для досить великих чисел. До N ~ 10⁴—10⁵ решето Ератосфена залишається найкращим^[2].

• Решето Сундарама
• Решето Аткіна