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

Рассмотрим метод нахождения положительных простых чисел, не превосходящих данного числа.

ПРЕДЛОЖЕНИЕ 1.11. Положительное составное число а имеет по крайней мере один положительный простой делитель, не превосходящий .

Доказательство. Среди отличных от единицы положительных делителей числа а существует наименьший; обозначим его через . Если бы число было составным, то оно имело бы положительный делитель q, удовлетворяющий условиям . В этом случае число q было бы положительным делителем числа а, меньшим , что противоречит выбору числа . Следовательно, — простое число. Если , то . Перемножая почленно и сокращая на b, получаем, .

ПРЕДЛОЖЕНИЕ 1.12. Если положительное число а, отличное от единицы, не делится ни на одно положительное простое число, не превосходящее , то оно простое.

Это предложение непосредственно следует из предложения 1.11. Существует простой метод составления таблицы положительных простых чисел, не превосходящих данного целого числа. Этот метод носит название решета Эратосфена.

Предположим, что надо найти все положительные простые числа, не превосходящие данного натурального числа а. Для этого выпишем подряд последовательность всех натуральных чисел от 2 до . В этой последовательности вычеркнем каждое второе число после 2. Первое незачеркнутое число — это простое число 3.

Далее вычеркнем каждое третье число после 3 (причем надо считать и те числа, которые уже вычеркнуты ранее). Первое следующее за 3 невычеркнутое число — это простое число 5. Вычеркнем каждое пятое число после 5, и т. п. Это вычеркивание продолжаем до тех пор, пока не дойдем до первого простого числа, не меньшего . В силу предложения 1.12 все числа, оставшиеся невычеркнутыми, будут положительными простыми, не превосходящими числа а.

Пример. Составим таблицу положительных простых чисел, не превосходящих 50. Для этого выпишем натуральные числа от 2 до 50 и произведем вычеркивание до встречи первого числа, большего или равного , т. е. до 11 (вычеркнутые числа — светлые):

Вычеркнем из этой последовательности каждое второе число после 2, далее — каждое третье число после трех, затем каждое пятое число после 5 и, наконец, каждое седьмое число после 7. Все числа, оставшиеся невычеркнутыми, будут простыми. Таким образом, получаем следующую таблицу положительных простых чисел, меньших 50: