Метод решета Эратосфена помогает находить простые числа путём постепенного отсеивания составных. 2

Алгоритм заключается в последовательной проверке делимости чисел на предстоящие простые числа. 2 Сначала берётся первое простое и из ряда натуральных чисел высеиваются все кратные ему. 2 Затем берётся следующее простое и отсеиваются все кратные ему и так далее. 2

Название «решето» метод получил потому, что во времена Эратосфена писали числа на дощечке, покрытой воском, и прокалывали дырочки в тех местах, где были написаны составные числа. 3 Поэтому дощечка являлась неким подобием решета, через которое «просеивались» все составные числа, а оставались только числа простые. 3