Нескінченість множини простих чисел. Решето Ератосфена.Давньогрецьких вчених зацікавило: скільки може бути простих чисел в натуральному ряді? Відповів на це питання Евклід, довівши, що множина простих чисел нескінченна. Теорема 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) всі числа, кратні простим числам, не більшим ніж , дістанемо за теоремою 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 (тобто кожне друге, починаючи з 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 Отримали всі прості числа на даному проміжку.
|