Решето Эратосфена
Материал из Википедии — свободной энциклопедии
В математике, решето́ Эратосфе́на — простой старинный алгоритм нахождения всех простых чисел до некоторого целого числа 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 (каждое второе, начиная с 22 = 4):
2 34567891011121314151617181920
Следующее невычеркнутое число 3 — простое. Пройдём по ряду чисел, вычёркивая все числа кратные 3 (каждое третье, начиная с 32 = 9):
2 34567891011121314151617181920
Следующее невычеркнутое число 5 — простое. Пройдём по ряду чисел, вычёркивая все числа кратные 5 (каждое пятое, начиная с 52 = 25). И т. д.
Необходимо провести вычёркивания кратных для всех простых чисел p, для которых 
. В результате все составные числа будут вычеркнуты, а невычеркнутыми останутся все простые числа. Для n = 20 уже после вычёркивания кратных числу 3 все составные числа получаются вычеркнутыми.
