2. Нескінченість множини простих чисел. Решето Ератосфена

Давньогрецьких вчених зацікавило: скільки може бути простих чисел в натуральному ряді? Відповів на це питання Евклід, довівши, що множина простих чисел нескінченна.

Теорема 2.1 (Евкліда). Множина простих чисел нескінченна.

Припустимо, що множина простих чисел скінчена. Нехай вона складається з простих чисел p₁, p₂, ..., р_п. Отже, ми припускаємо, що простих чисел, відмінних від p₁, p₂, ..., р_п, немає. Розглянемо тепер ціле число р = p₁ p₂, ... р_п. Очевидно, що це число відмінне від кожного з чисел p₁, p₂, ..., р_п. Оскільки число 1 не має дільників, відмінних від самого себе, то жодне з простих чисел p₁, p₂, ..., р_п не може бути дільником числа р. Ціле число р > 1. Тому воно або само просте, або за теоремою 3 ділиться на просте число, відмінне від кожного з чисел p₁, p₂, ..., р_п Звідси випливає, що існує принаймні одне просте число, відмінне від чисел p₁, p₂, ..., р_п а це суперечить нашому припущенню. Отже, наше припущення неправильне. Цим теорему доведено. Природно постає запитання: як у ряду натуральних чисел виділити всі прості числа?

Таблицю всіх простих чисел, що не перевищують даного натурального числа N, можна скласти так. Випишемо підряд усі натуральні числа від 2 до N:

2, 3, 4, 5, ..., N (1)

Потім закреслимо в ряду (1) всі числа, кратні 2, крім самого числа 2. Першим числом у ряду (1), яке залишилося після цього, є число 3. Число 3 не ділиться на 2, бо в противному разі ми закреслили б його: отже, число 3 ділиться лише на 1 і на самого себе, тому воно просте. Закреслимо тепер у ряду (1) всі числа, кратні 3, крім самого числа 3.

Першим числом, яке залишилося після цього в ряду (1), є число 5; воно не ділиться ні на 2, ні на 3, бо в противному разі воно виявилося б закресленим; отже, 5 ділиться тільки на 1 і на самого себе, тому воно просте число. Потім у ряду (1) закреслимо всі числа, кратні 5, крім самого числа 5 і т. д. Закресливши в ряду (1) всі числа, кратні простим числам, не більшим ніж , дістанемо за теоремою 4 таблицю всіх простих чисел, які не перевищують числа N.

Уперше для складання таблиць простих чисел описаний щойно метод застосував грецький математик Ератосфен. Ератосфен писав числа на папірусі, натягнутому на рамку; числа він не закреслював, а проколював. Внаслідок цього він діставав дещо схоже на решето: складені числа «просіювалися» крізь це решето, а прості числа залишалися. Тому цей метод називають решетом Ератосфена.

Метод Ератосфена поступово удосконалювався, завдяки чому складання таблиць простих чисел спрощувалося. Це, в свою чергу, дало можливість скласти таблиці простих чисел, що містять порівняно велику кількість чисел. Тепер складені таблиці простих чисел приблизно до 10 мільйонів. Приклад 1. Знайти прості чиста на проміжку [2, 30].

Запишемо натуральні числа починаючи від 2 до 30 в ряд:

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

Перше число у списку, 2 - Просте. Пройдемо по ряду чисел, закреслюючи всі числа кратні 2 (тобто кожне друге, починаючи з 2² = 4 ):

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

Наступне не закреслене число 3 - просте. Пройдемо по ряду чисел, закреслюючи всі числа кратні 3 (тобто кожне третє, починаючи з 3² = 9 ):

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

Наступне незакреслене число 5 - Просте. Пройдемо по ряду чисел, закреслюючи всі числа кратні 5 (тобто кожне пяте, починаючи з ² 5 = 25 ). І т. д. 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

Необхідно провести закреслення кратних для всіх простих чисел p , Для яких p ² ? n . У результаті всі складені числа будуть закреслені, а не закресленими залишаться всі прості числа. Для n=30 вже після закреслення кратних числу 5 всі складені числа виходять закресленими:

2 3 5 7 11 13 17 19 23 29

Отримали всі прості числа на даному проміжку.

Алгоритм пошуку простих чисел висіюванням

Для знаходження всіх простих чисел не більше заданого числа n, дотримуючись методу Ератосфена, потрібно виконати наступні кроки:

1) Виписати підряд всі цілі числа від 2 до n (2,3,4 ..., n)

2) Нехай змінна p спочатку дорівнює 2 - першому простому числу.

3) Викреслити зі списку всі числа від 2 p до n, що діляться на p (тобто, числа 2 p, 3 p, 4 p, ....)

4) Знайти перше не викреслене число, більше, ніж р, і привласнити значенням змінної p це число.

5) Повторювати кроки 3 та 4 до тих пір, поки p не стане більше, ніж n.

6) Всі не викреслені числа у списку - прості числа.

На практиці, алгоритм можна трохи покращити таким чином:

На кроці № 3, числа можна викреслювати, починаючи відразу з числа p² , тому що всі складові числа менше нього вже будуть викреслені до цього часу. І, відповідно, зупинити алгоритм можна, коли p² стане більше, ніж n.