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

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

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

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

1.   Перше просте число - два. Викреслимо всі числа більші двох, які діляться на два (4, 6, 8 …).

2.   Наступне число, яке залишилося незакресленим (три), є простим. Викреслюємо всі числа більші трьох та кратні трьом (6, 9 …).

3.   Наступне незакреслене число (п'ять) є простим. Викреслимо всі числа більші п'яти та кратні п'яти (10, 15, 20, 25 …).

4.   Повторюємо операцію поки не буде досягнуто число N:

·         Наступне незакреслене число є простим. Викреслимо всі числа більші нього та кратні йому.

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

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