Как мы уже говорили, существуют таблицы простых чисел, простирающиеся до очень больших чисел. Как можно было бы подступиться к составлению такой таблицы? Эта задача была, в известном смысле, решена (около 200 г. до н. э.) Эратосфеном, математиком из Александрии. Его схема состоит в следующем: напишем последовательность всех целых чисел от 1 до числа, которым мы хотим закончить таблицу:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

       2   2   2  3  2     2      2  3

Начнем с простого числа 2. Будем выбрасывать каждое второе число, начиная с 2 (кроме самого числа 2), т. е. чётные числа 4, 6, 8, 10 и т. д., подчеркивая каждое из них. После этой операции первым неподчёркнутым числом будет число 3. Оно простое, так как не делится на 2. Оставив число 3 неподчёркнутым, будем подчеркивать каждое третье число после него, т. е. числа 6, 9, 12, 15…; некоторые из них уже были подчеркнуты, поскольку они являются чётными. На следующем шаге первым неподчёркнутым числом окажется число 5; оно простое, так как не делится ни на 2, ни на 3. Оставим число 5 неподчёркнутым, но подчеркнем каждое пятое число после него, т. е. числа 10, 15, 20, 25…; как и раньше, часть из них уже оказалась подчёркнутой. Теперь — наименьшим неподчёркнутым числом окажется число 7. Оно простое, так как не делится ни на одно из меньших его простых чисел 2, 3, 5. Повторяя этот процесс, мы в конце концов получим последовательность неподчёркнутых чисел; все они (кроме числа 1) являются простыми.

Этот метод отсеивания чисел известен как «решето Эратосфена». Любая таблица простых чисел создается по этому принципу решета. В действительности, можно продвинуться гораздо дальше по ряду простых чисел, если использовать для их хранения память ЭВМ. Подобным образом, в Научно-исследовательской лаборатории Лос-Аламоса были получены все простые числа до 100 000 000.

Небольшое изменение метода решета позволит нам получить большую информацию. Предположим, что всякий раз, впервые подчеркивая числа, мы будем подписывать под ним простое число, с помощью которого оно отсеивается. Тогда 15 и 35 были бы записаны как

15, 35

 3   5

и т. д., как это показано на последовательности, выписанной выше. Таким образом, мы не только указали простые числа, но и для каждого составного числа привели наименьшее простое число, являющееся его делителем. Такой список чисел называется таблицей делителей. Таблица делителей является более сложной, чем таблица простых чисел. Чтобы немного упростить ее, обычно из нее исключают те составные числа, у которых простые делители малы, например, 2, 3, 5, 7. Самая большая такая таблица была вычислена на ЭВМ Д. X. Лемером и содержит все числа, вплоть до 10 000 000.

Как мы видели, решето Эратосфена может быть использовано для построения таблиц простых чисел и таблиц делителей. Однако оно может быть использовано и для теоретических исследований. Многие важные результаты в современной теории чисел были получены методом решета. Приведем результат, известный еще Евклиду:

Существует бесконечное число простых чисел.

Доказательство. Предположим, что существует только k простых чисел:

2, 3, 5…, р_k.

Тогда в решете не оказалось бы неподчёркнутых чисел, больших, чем р_k. Но это невозможно, так как произведение этих простых чисел

р = 2 • 3 • 5 • … • р_k

будет отсеиваться k раз, по разу для каждого простого числа, поэтому следующее число р + 1 не может быть подчеркнуто ни для одного из них.

Система задач 2.4.

1. Составьте таблицы простых чисел для каждой из сотен: 1—100, 101–200, … 901—1000.

2. Попытайтесь определить количество простых чисел в диапазоне 10001—10100.