Відкрити головне меню

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

МетодРедагувати

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

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

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

Оцінка складностіРедагувати

Алгоритм потребує   біт пам'яті та   математичних операцій.

Приклад для Редагувати

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

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

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

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

Наступне незакреслене число 3 — просте. Викреслимо всі числа кратні 3 (кожне третє, починаючи з  ):

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

Наступне незакреслене число 5 — просте. Викреслимо всі числа кратні 5 (кожне п’яте, починаючи з  ). І т. д.

Необхідно викреслити кратні для всіх простих чисел  , для яких  . В результаті всі складені числа будуть викреслені, а залишаться всі прості числа. Для   вже після викреслювання кратних числу 3 всі складені числа виявляються викресленими.

Алгоритм решета Ератосфена у вигляді програми на Python для пошуку простих чисел менших 1 000 000Редагувати

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

Див. такожРедагувати

ДжерелаРедагувати

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