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

“ Решето Ератосфена “ – спосіб складання таблиць простих чисел запропонований у ІІІ ст. до н.е. Ератосфеном.  
У стародавності писали на воскових табличках гострою паличкою - стилем. Тому Ератосфен, замість того щоб викреслювати написані їм на табличці числа, виколював їх гострим кінцем стилю. Після виколювання всіх складених чисел табличка нагадувала решето. З тих пір придуманий Ератосфеном метод відшукання простих чисел називають «решетом Ератосфена». 
Ось цей алгоритм:

1) Виписав підряд усі натуральні числа від 2 до п.
2) Залишав 2 і викреслював після нього всі числа через одне ( тобто парні числа: 4, 6, 8,…).
3) Залишав число 3 і викреслював після нього всі числа через два ( тобто 6, 9, 12,…).
4) Залишав число 5 і викреслював після нього всі числа через чотири (тобто 10, 15, 20,…) і т. д.

5) При цьому деякі числа викреслювалися один і більше разів, а не закреслені числа виявилися прості.   

Зараз для складання таблиць простих чисел використають ЕОМ. Уже є список перших 50 мільйонів цих чисел.