Нескінченість множини простих чисел. Решето Ератосфена.
Давньогрецьких вчених зацікавило: скільки може бути простих чисел в натуральному ряді? Відповів на це питання Евклід, довівши, що множина простих чисел нескінченна. Теорема 2.1 (Евкліда). Множина простих чисел нескінченна. □ Припустимо, що множина простих чисел скінчена. Нехай вона складається з простих чисел p1, p2,..., рп. Отже, ми припускаємо, що простих чисел, відмінних від p1, p2,..., рп, немає. Розглянемо тепер ціле число р = p1 p2,... рп. Очевидно, що це число відмінне від кожного з чисел p1, p2,..., рп. Оскільки число 1 не має дільників, відмінних від самого себе, то жодне з простих чисел p1, p2,..., рп не може бути дільником числа р. Ціле число р > 1. Тому воно або само просте, або за теоремою 3 ділиться на просте число, відмінне від кожного з чисел p1, p2,..., рп Звідси випливає, що існує принаймні одне просте число, відмінне від чисел p1, p2,..., рп а це суперечить нашому припущенню. Отже, наше припущення неправильне. Цим теорему доведено. ■ Природно постає запитання: як у ряду натуральних чисел виділити всі прості числа? Таблицю всіх простих чисел, що не перевищують даного натурального числа 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) всі числа, кратні простим числам, не більшим ніж Уперше для складання таблиць простих чисел описаний щойно метод застосував грецький математик Ератосфен. Ератосфен писав числа на папірусі, натягнутому на рамку; числа він не закреслював, а проколював. Внаслідок цього він діставав дещо схоже на решето: складені числа «просіювалися» крізь це решето, а прості числа залишалися. Тому цей метод називають решетом Ератосфена. Метод Ератосфена поступово удосконалювався, завдяки чому складання таблиць простих чисел спрощувалося. Це, в свою чергу, дало можливість скласти таблиці простих чисел, що містять порівняно велику кількість чисел. Тепер складені таблиці простих чисел приблизно до 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 (тобто кожне друге, починаючи з 22 = 4): 2 3 Наступне незакреслене число 3 - просте. Пройдемо по ряду чисел, закреслюючи всі числа кратні 3 (тобто кожне третє, починаючи з 32 = 9): 2 3 Наступне незакреслене число 5 - Просте. Пройдемо по ряду чисел, закреслюючи всі числа кратні 5 (тобто кожне п'яте, починаючи з 2 5 = 25). І т. д. 2 3 Необхідно провести закреслення кратних для всіх простих чисел p, Для яких p 2 ≤ n. У результаті всі складені числа будуть закреслені, а незакресленими залишаться всі прості числа. Для n =30 вже після закреслення кратних числу 5 всі складені числа виходять закресленими: 2 3 5 7 11 13 17 19 23 29 Отримали всі прості числа на даному проміжку.
|
, дістанемо за теоремою 4 таблицю всіх простих чисел, які не перевищують числа N.
