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

Решето́ Эратосфе́на, математический метод, позволяющий отсеивать составные числа из натурального ряда. Состоит в следующем. Выписываются все числа из некоторого отрезка ${\displaystyle 1,2,\ldots ,N}$ натурального ряда. Затем вычёркивается ${\displaystyle 1}$. Следующее число ${\displaystyle 2}$ – простое число. Затем вычёркиваются все натуральные числа, не превосходящие ${\displaystyle N}$ и делящиеся на ${\displaystyle 2}$. Число ${\displaystyle 3}$ – первое невычеркнутое число, является простым. Далее вычёркиваются все натуральные числа, не превосходящие ${\displaystyle N}$ и делящиеся на ${\displaystyle 3}$. Число ${\displaystyle 5}$ – следующее невычеркнутое число – является простым. Продолжая этот процесс, получают все простые числа, не превосходящие ${\displaystyle N}$, выбор которого произволен. Решето Эратосфена позволяет найти сколь угодно большой отрезок последовательности простых чисел. Метод предложен Эратосфеном. Решето Эратосфена как теоретический метод в теории чисел был развит норвежским математиком В. Бруном (1919).