Просте число — це натуральне число, яке має рівно два різні натуральні дільники (лише 1 і саме число).
Решту чисел, окрім одиниці та нуля, називають складеними. Таким чином, всі натуральні числа, більші від одиниці, розбивають на прості і складені. Теорія чисел вивчає властивості простих чисел. В теорії кілець простим числам відповідають незвідні елементи.
Послідовність простих чисел починається так:
Основна теорема арифметики стверджує, що кожне натуральне число більше одиниці (1), можна представити як добуток простих чисел, причому, в єдиний спосіб з точністю до порядку множників. Таким чином, прості числа — це елементарні «будівельні блоки» натуральних чисел.
Представлення натурального числа у вигляді добутку простих називають розкладом на прості або факторизацією числа. Тепер невідомі Поліноміальні алгоритми факторизації чисел, хоча і не доведено, що таких алгоритмів не існує (тут і далі мова йде про поліноміальною залежності часу роботи алгоритму від логарифма розміру числа, тобто від кількості його цифр). На припущенні про високу обчислювальну складність задачі факторизації базується криптосистема RSA.
Решето Ератосфена, решето Сундарама та решето Аткіна дають прості способи складання початкового списку простих чисел до певного значення.
Однак на практиці замість отримання списку простих чисел найчастіше потрібно перевірити, чи є дане число простим. Алгоритми, які вирішують це завдання, називають тестами простоти. Існує безліч поліноміальних тестів простоти, але більшість з них є стохастичними (наприклад, тест Міллера — Рабина) і використовуються для потреб криптографії. Тільки в 2002 році було доведено, що завдання перевірки на простоту в загальному вигляді можна розв'язати за поліноміальний час, але запропонований детермінований алгоритм має досить велику складність, що ускладнює його застосування на практиці.
Для деяких класів чисел існують спеціалізовані ефективні тести простоти. Наприклад, для перевірки на простоту чисел Мерсенна використовують тест Люка — Лемера, а для перевірки на простоту чисел Ферма — тест Пепіно.
Простих чисел нескінченно багато. Найдавніше відоме доведення цього факту дав Евклід у «Началах» (книга IX, твердження 20). Його доведення може бути коротко відтворено так:
Математики пропонували інші доведення. Одне з них (наведене Ейлером) показує, що сума всіх чисел, обернених до простих є розбіжною.
Відома теорема про розподіл простих чисел стверджує, що кількість простих чисел менших за n, яку позначають як , зростає як , тобто
Здавна ведуться записи, в яких відзначають найбільші відомі на той час прості числа. Один з рекордів поставив свого часу Ейлер, знайшовши просте число .
Найбільшим відомим простим числом станом на червень 2009 року є . Воно складається з 12 978 189 десяткових цифр і є простим числом Мерсенна (M43112609). Його знайшли 23 серпня 2008 року на математичному факультеті університету UCLA в рамках проєкту з розподіленого пошуку простих чисел Мерсенна GIMPS. Попереднє за величиною відоме просте, також є простим числом Мерсенна M37156667, було знайдено 6 вересня 2007 року учасником проекту GIMPS Гансом-Міхаелем Елвеніхом (нім. Hans-Michael Elvenich).
7 січня 2016 був поставлений новий рекорд: проект GIMPS знайшов ще більше просте число: , що складається з 22 338 618 десяткових цифр. Нове просте число також є простим числом Мерсенна — M74207281. Нове просте число було обчислене множенням 74 207 281 двійок та відніманням 1. Перевірка простоти тривала 31 добу безперервних обчислень на комп'ютері з процесором Intel I7-4790. Результати перевірки були незалежно підтверджені іншими розробниками з використанням іншого апаратного та програмного забезпечення.
Числа Мерсенна вигідно відрізняються від решти наявністю ефективного тесту простоти: тесту Люка — Лемера. Завдяки йому прості числа Мерсенна давно утримують рекорд як найбільші відомі прості.
За знаходження простих чисел з понад 100 000 000 та 1 000 000 000 десяткових цифр EFF призначила грошові призи в 150 000 та 250 000 доларів США відповідно.
Досі існує багато відкритих запитань щодо простих чисел, найвідоміші з яких були перераховані Едмундом Ландау на П'ятому Міжнародному математичному конгресі :
Відкритою проблемою є також існування нескінченної кількості простих чисел у багатьох цілочисельних послідовностях, включаючи числа Фібоначчі, числа Ферма і т. д.
Великі прості числа (порядку ) використовують в криптографії з відкритим ключем. Прості числа також використовують в хеш-таблицях і для генерації псевдовипадкових чисел (зокрема, в генераторі псевдовипадкових чисел Вихор Мерсенна).
Цей розділ не містить посилань на джерела. (Квітень 2020) |
#include bool is_prime(int const num) { if (num <= 3) { return num > 1; } else if (num % 2 == 0 || num % 3 == 0) { return false; } else { for (int i = 5; i * i <= num; i += 6) { if (num % i == 0 || num % (i + 2) == 0) { return false; } } return true; } }
Математичний Папірус Рінда, що має вік близько від 1550 р.до.н.е, описує різні форми розкладання єгипетських дробів для простих і складених чисел. Однак, найбільш ранній відомий запис про явне дослідження простих чисел належить до математики Стародавньої Греції. Евклід у своїй роботі Елементи (близько 300 р.до.н.е.) довів нескінченність простих чисел і основну теорему арифметики, і показав як побудувати досконале число із Числа Мерсенна.
Більшість філософів стародавньої Греції навіть не розглядали 1 як число, тому вони навіть не розглядали чи є воно простим. Декілька математиків тих часів вважали, що прості числа є підмножиною непарних чисел, тому вони також не розглядали випадок що число 2 може бути простим. Однак, Евклід і більшість інших Грецьких математиків розглядали 2 як просте число. Ісламські математики середньовіччя здебільшого наслідували Греків і також не розглядали число 1 як число. У середні віки і в часи Ренесансу математики почали ставитися до 1 як до числа, і деякі з них відносили його до першого простого числа. У середині 18-го століття Християн Гольдбах перелічив число 1 як просте у своєму листуванні з Леонардом Ейлером; однак сам Ейлер не розглядав 1 як просте. В 19-му столітті багато математиків досі продовжували вважати число 1 простим, а переліки простих чисел, в яких включали 1 продовжували публікувати до 1956 р.
Якби визначення простих чисел було змінене, так щоб до них віднести одиницю, багато тверджень, які стосуються простих чисел необхідно було б переформулювати у досить не зручний спосіб. Наприклад, основну теорему арифметики необхідно було б перефразувати так щоб розкладання виконувалося у прості множники що більші за 1, оскільки кожне число мало б множину способів розкладання із різною кількістю повторених 1. Аналогічно, не правильно б працювало Решето Ератосфена якби число 1 вважалося простим, оскільки в ньому усі числа є кратними 1 і результатом було б лише одне число 1. Деякі інші властивості простих чисел також не виконуються для випадку з 1: наприклад, формули для Функції Ейлера або для суми функції дільників відрізняються для простих чисел і для 1. До початку 20-го століття, математики дійшли згоди, що число 1 не повинне належати до простих чисел, а скоріше належить до своєї власної окремої категорії "одиниці".
Вікіцитати містять висловлювання на тему: Просте число |
Вікіпідручник має книгу на тему |
This article uses material from the Wikipedia Українська article Просте число, which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). Вміст доступний на умовах CC BY-SA 4.0, якщо не вказано інше. Images, videos and audio are available under their respective licenses.
®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki Українська (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.