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

Решето́ Ератосфе́на в математиці — простий стародавній алгоритм знаходження всіх простих чисел менших деякого цілого числа $n$ , що був створений давньогрецьким математиком Ератосфеном.

Метод[ред. | ред. код]

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

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

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

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

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

Оцінка складності[ред. | ред. код]

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

Приклад[ред. | ред. код]

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

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

Перше число в рядку 2 — просте. Викреслимо всі числа кратні 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^{2}=9$ ):

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

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

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

Реалізація алгоритму решета Ератосфена[ред. | ред. код]

Псевдокод[ред. | ред. код]

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

Алгоритм Решето Ератосфена є   вхід : ціле число n > 1.   вихід : всі прості числа від 2 до n.    нехай A — масив булевих значень, індексованих цілим числом s від 2 до n,   ініціалізуємо весь масив значеннями true.      для i = 2, 3, 4, ..., що не перевищує  $\sqrt n$  робити     якщо А [i] є true       для j = i², i² + i, i² + 2i, i² + 3i, ..., що не перевищує n робити                 A[j] := false    повернути всі i де A[i] є true.

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

Python[ред. | ред. код]

Реалізація мовою 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

Див. також[ред. | ред. код]

Джерела[ред. | ред. код]

↑ Weisstein, Eric W. Sieve of Eratosthenes(англ.) на сайті Wolfram MathWorld.
↑ ^а ^б ^в Jonathan Sorenson, An Introduction to Prime Number Sieves, Computer Sciences Technical Report #909, Department of Computer Sciences University of Wisconsin-Madison, January 2, 1990 (the use of optimization of starting from squares, and thus using only the numbers whose square is below the upper limit, is shown).
↑ Sedgewick, Robert (1992). Algorithms in C++. Addison-Wesley. ISBN 978-0-201-51059-1., p. 16.

[1] Weisstein, Eric W. Sieve of Eratosthenes(англ.) на сайті Wolfram MathWorld.

[intro-2] а ^б ^в Jonathan Sorenson, An Introduction to Prime Number Sieves, Computer Sciences Technical Report #909, Department of Computer Sciences University of Wisconsin-Madison, January 2, 1990 (the use of optimization of starting from squares, and thus using only the numbers whose square is below the upper limit, is shown).

[sedgewick-3] Sedgewick, Robert (1992). Algorithms in C++. Addison-Wesley. ISBN 978-0-201-51059-1., p. 16.

[1]

[2]

[3]