Page 42 - 4570

41

У багатьох книгах з теорії чисел наводяться таблиці натуральних простих
чисел, що не перевищують даного числа N. Простий метод побудови таких
таблиць запропонував близько 200 р. до н .е. грецький математик із Александрії
Ератостен. Цей метод, відомий під назвою «решета Ератостена», виглядає так.
Випишемо підряд всі натуральні числа від 2 до N. Число 2 як просте
залишимо, а всі інші парні числа викреслимо. Перше не закреслене число після
2 це просте число 3. Після цього викреслимо кожне третє число після 3 (при
цьому треба рахувати також і ті числа, що їх викреслено раніше). Першим
незакресленим числом після 3 буде число 5. Воно знову просте. Тепер
викреслимо кожне п’яте число після 5, і т. д. Якщо в такий спосіб знайдено всі
прості числа до числа р включно, а потім викреслено всі числа, які більші р і
кратні р. то перше не закреслене після р число знову буде простим (бо воно не
ділиться на жодне менше просте число). Продовжуючи таке викреслювання,
доки це можливо, врешті решт одержимо всі прості числа, які не перевищують
N.
Зауваження. Досить викреслювати кратні лише тих простих чисел, які не
перевищують N . Це значно зменшує обсяг обчислень.
Приклад 1.57. За допомогою «решета; Ератостена» знайти всі прості числа
з проміжку [1230; 1250].

Розв ’язання. Оскільки 1250 < 36. то з проміжку [1230; 1250] досить
викреслити кратні лише тих простих чисел, що не перевищують 35, тобто
кратні чисел 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 і 31. Після викреслювання чисел,
кратних 2, 3 і 5, невикресленими залишаться тільки числа 1231, 1237, 1241,
1243, 1247 і 1249. Остачі відділення 1230 на прості числа 7, 11, 13, 17, 19, 23, 29
і 31 дорівнюють відповідно 5, 9, 8, 6, 14, 11, 12 і 21. Тому на проміжку [1230;
1250] кратними цих простих чисел будуть:

число р його кратні число р його кратні

7 1232, 1239, 1246 19 1235
11 1232, 1243 23 1242
13 1235, 1248 29 1247
17 1241 31 1240

Якщо викреслити й ці кратні, то невикресленими залишаться числа 1231,
1237 і 1249. Вони і є шуканими.
Занумеруємо натуральні прості числа у порядку їх зростання: р 1 =2, р 2 = 3,
р 3 = 5, .... Коли продовжити цей ряд досить далеко, то кидається у вічі
нерегулярність, з якою прості числа розподілені серед натуральних. Є
проміжки, на яких прості числа зустрічаються часто, і не тільки на початку
натурального ряду. Наприклад, по 4 простих числа містить кожен із проміжків
[5651; 5659] і [299471; 299479]. Нерідко трапляються пари простих чисел, які
відрізняються одне від одного лише на 2, як, скажімо, 17 і 19 або 4091 і 4093
(такі пари простих чисел називають «близнятами», в межах першого мільйона
їх 8164. Досі невідомо, чи таких пар скінченна кількість).