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

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

Метод

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

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

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

Оцінка складності

Алгоритм потребує $O(N)$ біт пам'яті та $O(N\log \log 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^{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 всі складені числа виявляються викресленими.

Реалізація алгоритму решета Ератосфена

Псевдокод

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

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

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

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

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

Python

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

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

Див. також

Джерела

Weisstein, Eric W. Sieve of Eratosthenes(англ.) на сайті Wolfram MathWorld.
Sedgewick, Robert (1992). Algorithms in C++. Addison-Wesley. ISBN 978-0-201-51059-1., p. 16.
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).

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

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

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

[intro-3] 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).