4. Как можно найти все простые числа, меньшие данного числа?

Способ, о котором будет идти речь, известен был ужев древности: он носит название решета Эратосфена.

Предположим, что мы хотим найти все простые числа, не превосходящие некоторого натурального числа а. С этой целью выпишем все последовательные натуральные числа от 1 до а и будем вычеркивать из этой последовательности все числа, которые не являются простыми: прежде всего число 1, а затем для каждого натурального числа все числа, большие чем и делящиеся на Легко видеть, что таким путем каждое составное число окажется вычеркнутым и останутся только простые числа.

Итак, из последовательности 1, 2, 3, 4,..., а мы вычеркнем число 1, затем числа, большие чем 2 и делящиеся на 2, далее числа, большие чем 3 и делящиеся на 3. Чисел, делящихся на 4, вычеркивать нам уже не придется, так как они вычеркнуты как числа и делящиеся на 2. Таким образом, далее мы будем вычеркивать числа, большие чем 5 и делящиеся на 5 и т. д. При этом мы можем уже не вычеркивать ни одно из чисел Действительно, если составное число а и то, согласно теореме 2, число имеет простой делитель следовательно, и число окажется вычеркнутым как число, большее и делящееся на

Так, например, желая получить все простые числа , вычеркнем из последовательности число 1, затем числа и делящиеся на 2, далее числа и делящиеся на 3, затем числа и делящиеся на 5 и, наконец, числа и делящиеся на 7. Все числа, оставшиеся в нашей последовательности, будут простыми. Таким путем мы получим следующую последовательность (в которой все простые числа выделены жирным шрифтом):

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66.

67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100.

Обозначим по порядку простое число через Тогда Легко можно подсчитать, что

В 1909 г. были изданы таблицы простых чисел, меньших 10 миллионов, в которых для каждого натурального числа не делящегося на 2, 3, 5 или 7, дается его наименьший простой делитель. В 1951 г. были опубликованы таблицы простых чисел до миллиона.

Якуб Филипп Кулик (1793—1863 гг.) составил таблицы простых чисел, содержащихся в первых ста миллионах. Эти таблицы после проверки были исиользоваиы при составлении таблиц простых чисел миллиона, изданных в 1951 г. Недавно (1959 г.) К. Л. Бейкер и Ф. Ю. Груибергер составили микрофильм, содержащий все простые числа .