Главная > Что мы знаем и чего не знаем о простых числах
<< Предыдущий параграф Следующий параграф >>
Пред.
След.
Макеты страниц

Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше

Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике

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 г.) К. Л. Бейкер и Ф. Ю. Груибергер составили микрофильм, содержащий все простые числа .

Categories

1
Оглавление
email@scask.ru