Перевірка простих чисел
Перевірте, чи є число простим, і знайдіть його множники. Безкоштовний онлайн-калькулятор для миттєвої перевірки будь-якого числа.
Що таке просте число?
Просте число — природне число більше 1, яке має саме дві різні множники: 1 і саме воно. Перші прості числа: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97...
Ключові факти про прості числа:
- 2 є єдиним парним простим числом. Всі інші парні числа ділиться на 2, тому мають більше двох множників.
- 1 не є простим за сучасною конвенцією. Вилучення 1 зберігає унікальність факторизації на прості числа (Фундаментальна теорема арифметики).
- Прості числа нескінченно багато. Євклід довів це близько 300 до н. е.: припустімо, що існує скінченний перелік всіх простих чисел p₁, p₂, ..., pₙ. Тоді число (p₁ × p₂ × ... × pₙ) + 1 either є простим або має простий множник, який не належить до списку — протиріччя. Тому перелік нескінченний.
- Зростають числа, прості числа стають рідше — але вони ніколи не припиняються. Є 25 простих чисел менше 100, 168 менше 1 000, а 78 498 менше 1 000 000.
Складне число — будь-яке позитивне ціле число більше 1, яке не є простим — воно має хоча б один множник, окрім 1 і самого себе. Наприклад, число 12 складне, оскільки 12 = 2 × 6 = 3 × 4 = 2 × 2 × 3. кожне складне число має унікальну факторизацію на прості числа (Фундаментальна теорема арифметики).
Як перевірити, чи є число простим
Є кілька методів перевірки простоти, що різняться від простої перевірки ділення до складних алгоритмів:
Перевірка ділення (базовий метод): Перевірте, чи діляться ли цілі числа від 2 до √n рівномірно. Якщо ні, то n є простим. Ви повинні перевірити тільки до √n, оскільки якщо n = a × b з a ≤ b, тоді a ≤ √n. Якщо не знайдено жодного дільника до √n, то немає жодного вище √n.
Оптимізована перевірка ділення: Після перевірки ділення на 2 перевірте тільки непарні числа. Далі: перевірте 2, 3, потім тільки числа форми 6k±1 (оскільки всі прості числа більше 3 мають цю форму). Це зменшує кількість перевірок на близько 66% порівняно з простою перевіркою ділення.
| Число | √n (приблизно) | Перевірка дільників до | Просте? |
|---|---|---|---|
| 97 | 9,85 | 2, 3, 5, 7 | Так (ніякі не діляться рівномірно) |
| 91 | 9,54 | 2, 3, 5, 7 | Ні (7 × 13 = 91) |
| 1 009 | 31,76 | До 31 | Так (просте) |
| 1 001 | 31,64 | До 31 | Ні (7 × 11 × 13 = 1 001) |
| 7 919 | 88,99 | До 89 | Так (1000-те просте число) |
Для великих чисел (сотні тисяч цифр) перевірка ділення стає комп'ютерно не здійснимою. Використовуються складніші методи, такі як тест простоти Міллера-Рабіна (випадковий, використовується в криптографії) та тест простоти АКС (детермінований поліноміальний час, 2002).
Кожне складне число можна записати як унікальний добуток простих чисел — його факторизацію на прості числа. Це гарантовано забезпечується фундаментальним теоремою арифметики. Для знаходження факторизації на прості числа знову і знову ділять на найменше просте число: Факторизація на прості числа використовується для знаходження найбільшого спільного діільника (НСД) і найменшого спільного кратного (НСК) чисел. НСД(12, 18) = 2² × 3? Ні — візьміть мінімальну потужність спільних простих чисел: НСД = 2¹ × 3¹ = 6. НСК бере максимальну потужність: НСК(12, 18) = 2² × 3² = 36. Прості числа — це «атоми» арифметики — фундаментальна теорема арифметики стверджує, що кожне позитивне ціле число більше 1 є або простим або може бути виражене як унікальний добуток простих чисел. Ця унікальність робить прості числа нерозбивними будівельними блоками всіх чисел. Сучасна інтернет-безпека залежить від простих чисел. Алгоритм RSA (використовується для HTTPS, шифрування електронної пошти та цифрових підписів) генерує публічні ключі шляхом множення двох великих простих чисел p і q для формування n = p × q. Ключі шифрування та розшифрування обчислюються за допомогою модулярної арифметики з n. Безпека ґрунтується на проблемі факторизації цілих чисел: при заданому n (ціле число з 2048 бітом із ~617 десятковими цифрами), знаходження p і q є комп'ютерно не здійснимим за сучасними технологіями. Диффі-Геллманів обмін ключами використовує великі прості модулі для безпечної домовленості щодо ключів. Коли ви підключаєтесь до вебсайту за HTTPS, прості числа безпечно захищають дані в реальному часі. Таблиці хешування використовують прості розміри масивів для мінімізації колізій. Коли функція хешування відображає ключі в індекси вмісту, використання простого числа вмостей забезпечує краще розподілення тому, що прості числа мають жодних факторів, які могли б створювати систематичні шаблони колізій. Псевдовипадові генератори чисел (ПВГЧ) використовують прості модулі в лінійних конгруенційних генераторах та інших алгоритмах. Період (до повторення) таких генераторів часто дорівнює простому модулюючому числу мінус 1. У нескінченному наборі простих чисел певні підмножини мають особливі властивості або значення: Мерсеннові прості числа (2ⁿ − 1) мають особливе значення тому, що вони можуть бути перевірені на простоту за допомогою ефективного тесту Лукаса-Лемера. Проект GIMPS (Великий інтернет-пошук Мерсенна простих чисел) використовує розподілену обробку даних у світі для знаходження нових Мерсенна простих чисел. На 2024 рік найбільше відоме Мерсенна просте число — 2^136,279,841 − 1, яке має понад 41 мільйон десяткових цифр. Товсті прості числа (пари, що різняться на 2) передбачається, що вони нескінченно багато (гіпотеза про товсті прості числа), але ця гіпотеза залишається нерозв'язаною — однією з найвідоміших відкритих проблем у математиці. У 2013 році Їтанг Цзян довів слабшу версію, що існує нескінченно багато пар простих чисел, що різняться на не більше 70 мільйонів, яка пізніше була покращена до 246. Прості числа стають рідкіснішими при зростанні чисел, але їх розподіл слідує статистичним законам, описаним в теорії простих чисел: Теорія простих чисел (доказана незалежно від Гадамарда і де ла Валле-Пуссена в 1896 році) стверджує, що кількість простих чисел до N, позначеної π(N), приблизно дорівнює N / ln(N) для великого N: Гіпотеза Рімана — одна з проблем тисячоліття зі страхуванням в розмірі мільйона доларів — стосується точного розподілу простих чисел. Вона передбачає, що всі нон-тривіальні нулі функції Рімана мають дійсну частину 1/2. Це пов'язано з тим, як "случайний" виглядає розподіл простих чисел — гіпотеза передбачає оптимальну регулярність між простими інтервалами. Ні. За сучасною математичною конвенцією, 1 не є ні простим, ні складеним. Вилучення 1 із простих зберігає унікальність факторизації (фундаментальна теорема арифметики) — якщо б 1 було простим, кожне число мало б нескінченно багато факторизацій (наприклад, 6 = 2×3 = 1×2×3 = 1×1×2×3 = ...). Історично деякі математики вважали 1 простим, але сучасна назва виключає його. На сьогодні 2024 року найбільше відоме просте число — 2^136,279,841 − 1 (Мерсеннове просте число), відкрито у жовтні 2024 року. Воно має понад 41 мільйон цифр. Проект Великий інтернетовий пошук Мерсена (GIMPS) знаходить більшість рекордних простих чисел за допомогою розподіленого обчислення від волонтерів по всьому світу. Ці величезні прості числа не мають практичних застосувань — їх пошук здійснюється лише для математичної експлуатації. Прості числа здаються нерегулярними, але існують шаблони. Всі прості числа > 5 закінчуються на 1, 3, 7 або 9 (ніколи не 0, 2, 4, 5, 6, 8). Всі прості числа > 3 мають вигляд 6k±1. Двійні прості числа (різні на 2, наприклад 11 і 13) здаються продовжуватися назавжди (неповірена гіпотеза про двійні прості числа). Твердження про прості числа описує статистичну щільність простих чисел біля N як близько 1/ln(N). Так, 2 є простим — і це єдине парне просте число. 2 має лише два множники (1 і 2), задовольняючи визначення. Всі інші парні числа діляться на 2, роблячи їх складеними. Простота 2 є особливим випадком, який часто потрібно обробляти окремо в алгоритмах і доведеннях. RSA шифрування генерує пару ключів шляхом: (1) вибору двох великих простих чисел p і q (кожне 1024+ біта), (2) обчислення n = p×q, (3) отримання шифрування ключа e і ключа декодування d за допомогою модулярної арифметики. Хтось може шифрувати за допомогою n і e (відкритий ключ), але тільки власник p і q (або d) може розшифрувати. Безпека ґрунтується на складності факторизації n у p×q. Для малих чисел (до ~10^12): оптимізована перевірка ділення тільки до √n за допомогою шаблону 6k±1. Для середніх чисел: тест простоти Міллера-Рабіна з кількома свідками дуже швидкий, але ймовірний. Для дуже великих чисел (криптографічні розміри, 1000+ цифр): ймовірніші тести, такі як Міллер-Рабіна з багатьма випадковими свідками, або тест AKS для детермінованого доведення. Проста різниця — різниця між двома послідовними простими числами. Найменша проста різниця становить 1 (між 2 і 3), а всі інші послідовні прості числа мають різниці не менше 2 (оскільки одне повинно бути нечітким). Різниці зростають повільно в середньому: біля N, середня різниця між простими числами становить ln(N). Високопрості різниці існують — існують довільно довгі послідовності послідовних складених чисел (наприклад, n!+2, n!+3, ..., n!+n є складеними для будь-якого n). 100 = 2 × 50 = 2 × 2 × 25 = 2 × 2 × 5 × 5 = 2² × 5². Прості множники 100 — 2 і 5. Ця факторизація пояснює чому 100 діляться рівно на 1, 2, 4, 5, 10, 20, 25, 50 і 100 — кожен дільник відповідає комбінації 2⁰˒¹˒² і 5⁰˒¹˒². Гіпотеза Ґольдбаха (1742) стверджує, що кожне парне число більше 2 можна виразити як суму двох простих чисел. Наприклад: 4=2+2, 6=3+3, 8=3+5, 10=3+7, 100=3+97=11+89=17+83. Вона була перевірена комп'ютерно до 4×10^18, але залишається нерозв'язаною. Вона є однією з найстаріших і найвідоміших нерозв'язаних проблем теорії чисел. Існує нескінченно багато простих чисел — Євклід довів це близько 300 до н. е. Доведення за суперечністю: якщо б існувало скінченне число простих чисел, їхній добуток плюс 1 був би або простим, або мав би простий множник, який не належав до уявленого повного списку, що призводить до суперечності. Хоча прості числа стають рідкіснішими при більших числах, вони ніколи не припиняються. Є саме 78,498 простих чисел менше 1,000,000 і 5,761,455 простих чисел менше 100,000,000.Факторування на прості числа
Число Факторизація на прості числа Розбивка на дерево факторів 12 2² × 3 12 → 4×3 → 2×2×3 60 2² × 3 × 5 60 → 4×15 → 2²×3×5 100 2² × 5² 100 → 4×25 → 2²×5² 360 2³ × 3² × 5 360 → 8×45 → 2³×3²×5 1024 2¹⁰ Всі прості фактори — 2 2310 2 × 3 × 5 × 7 × 11 Добуток перших 5 простих чисел Чому прості числа мають значення: застосування в математиці та техніці
Види простих чисел
Тип Опис Приклади Товсті прості числа Прості числа, що різняться на 2 (3,5), (11,13), (17,19), (41,43) Мерсеннові прості числа Прості числа форми 2ⁿ − 1 3, 7, 31, 127, 8191 Ферматівські прості числа Прості числа форми 2^(2ⁿ) + 1 3, 5, 17, 257, 65537 Софійські прості числа p і 2p+1 є простими 2, 3, 5, 11, 23, 29 Палиндромні прості числа Прості числа, які читаються тією ж самою літерою зліва направо 11, 101, 131, 151, 181 Безпечні прості числа Прості числа p, де (p−1)/2 також є простим 5, 7, 11, 23, 47, 59 Розподіл простих чисел
N Дійсна π(N) Приблизна N/ln(N) Густота 100 25 21.7 1 на 4 1,000 168 144.8 1 на 6 10,000 1,229 1,085.7 1 на 8 100,000 9,592 8,685.9 1 на 10 1,000,000 78,498 72,382.4 1 на 13 1,000,000,000 50,847,534 48,254,942 1 на 20 Часто запитані питання
Чи є 1 простим числом?
Яке найбільше відоме просте число?
Є лишилися шаблони в простих числах?
Чи є 2 простим числом?
Як використовується простота в шифруванні?
Яка найшвидша методика перевірки, чи є число простим?
Що таке проста різниця?
Що є простими множниками 100?
Що таке гіпотеза Ґольдбаха?
Скільки існує простих чисел?
{ “@context”: “https://schema.org”, “@type”: “FAQPage”, “mainEntity”: [ { “name”: “Чи є 1 простим числом?”, “acceptedAnswer”: { “@type”: “Answer”, “text”: “Ні. За сучасною математичною конвенцією, 1 не є ні простим, ні складеним.” } }, { “name”: “Яке найбільше відоме просте число?”, “acceptedAnswer”: { “@type”: “Answer”, “text”: “На сьогодні 2024 року найбільше відоме просте число — 2^136,279,841 − 1 (Мерсеннове просте число), відкрито у жовтні 2024 року.” } }, { “name”: “Є лишилися шаблони в простих числах?”, “acceptedAnswer”: { “@type”: “Answer”, “text”: “Прості числа здаються нерегулярними, але існують шаблони.” } }, { “name”: “Чи є 2 простим числом?”, “acceptedAnswer”: { “@type”: “Answer”, “text”: “Так, 2 є простим — і це єдине парне просте число.” } }, { “name”: “Як використовується простота в шифруванні?”, “acceptedAnswer”: { “@type”: “Answer”, “text”: “RSA шифрування генерує пару ключів шляхом: (1) вибору двох великих простих чисел p і q (кожне 1024+ біта), (2) обчислення n = p×q, (3) отримання шифрування ключа e і ключа декодування d за допомогою модулярної арифметики.” } }, { “name”: “Яка найшвидша методика перевірки, чи є число простим?”, “acceptedAnswer”: { “@type”: “Answer”, “text”: “Для малих чисел (до ~10^12): оптимізована перевірка ділення тільки до √n за допомогою шаблону 6k±1.” } }, { “name”: “Що таке проста різниця?”, “acceptedAnswer”: { “@type”: “Answer”, “text”: “Проста різниця — різниця між двома послідовними простими числами.” } }, { “name”: “Що є простими множниками 100?”, “acceptedAnswer”: { “@type”: “Answer”, “text”: “Прості множники 100 — 2 і 5.” } }, { “name”: “Що таке гіпотеза Ґольдбаха?”, “acceptedAnswer”: { “@type”: “Answer”, “text”: “Гіпотеза Ґольдбаха стверджує, що кожне парне число більше 2 можна виразити як суму двох простих чисел.” } }, { “name”: “Скільки існує простих чисел?”, “acceptedAnswer”: { “@type”: “Answer”, “text”: “Існує нескінченно багато простих чисел.” } } ] }
Прості числа в теорії чисел та нерозв'язані проблеми
Прості числа знаходяться в центрі деяких з найбільш красивих та найбільш уперто нерозв'язаних проблем математики. Зрозуміння цих відкритих питань світить на те, скільки ми знаємо про прості числа — і скільки залишається загадкою, незважаючи на століття зусиль.
Гіпотеза Рімана (1859): Функція Рімана ζ(s) = Σ(1/nˢ) пов'язана із розподілом простих чисел через її нулі. Гіпотеза стверджує, що всі нон-тривіальні нулі знаходяться на критичній лінії Re(s) = 1/2. Якщо вона вірна, то вона забезпечить найточніше можливе описання розподілу простих чисел. Більше 10 трілліонів нулів були обчислені і всі знаходяться на критичній лінії — але немає жодного доведення. Це є однією з проблем тисячоліття, яка має нагороду в розмірі $1 мільйона від Інституту Клейа з математики.
Двійна гіпотеза про прості числа: Чи існують нескінченно багато пар простих чисел (p, p+2) — наприклад, (11,13), (17,19), (41,43), (101,103)? Гіпотеза каже так, але вона залишається нерозв'язаною. У 2013 році Янґ Цзінґ зробив прорив, довівши існування нескінченно багатьох пар простих чисел з розривом не більше 70 мільйонів — перша коли-небудь обмежена межа. Проект Полімат згодом зменшив цю межу до 246, що означає, що ми знаємо існування нескінченно багатьох пар простих чисел з розривом ≤ 246. Розрив 2 залишається нерозв'язаним.
Гіпотеза Ґольдбаха (1742): кожне парне число більше 2 є сумою двох простих чисел. Верифіковано комп'ютерно до 4 × 10^18. Кожне перевірене раніше парне число задовольняє їй — часто багатьма способами (100 = 3+97 = 11+89 = 17+83 = 29+71 = 41+59 = 47+53). Але немає жодного доведення, яке охоплює всі парні числа. "Слабка гіпотеза Ґольдбаха" (кожне нечітке число ≥ 7 є сумою трьох простих чисел) була доведена в 2013 році Гаральдом Гельфготтом.
Прості числа Мерсенна та досконалі числа: Просте число Мерсенна є однією з форм 2ⁿ − 1 (де n самому має бути простим). Перші кілька: 3, 7, 31, 127, 8191. Відомо лише 52 такі числа на 2024 рік. Прості числа Мерсенна пов'язані з досконалими числами: кожне просте число Мерсенна генерує навіть досконале число за допомогою формули 2^(p−1) × (2^p − 1). Число 28 = 4 × 7 (за допомогою простого числа Мерсенна 7) і 496 = 16 × 31 (за допомогою простого числа Мерсенна 31) є досконалими числами. Чи існують нескінченно багато простих чисел Мерсенна? Нерозв'язане.
Гіпотеза ABC та її наслідки: Гіпотеза ABC (заявлена в 1985 році) є глибокою взаємозв'язанністю щодо простої факторизації трьох чисел a + b = c. Якщо вона буде доведена, то вона передбачатиме теорему Ферма та багато інших результатів як прості наслідки. У 2012 році Сінічі Мочізуку опублікував запропоноване доведення за допомогою своєї теорії інтеруніверсальної Тейхмюллера — але доведення таке нове та складне, що спільнота математиків протягом десяти років обговорювала його справжність, деякі математики приймають його, а інші знаходять розрив.
Прості числа залишаються найвищою математичною загадкою: просте визначення (число з точно двома множниками), але розподіл їх досить складний, щоб підкреслювати відкриті проблеми, які протягом століть чинили опір найкращим математикам. Кожен новий рекордний простий чисел, кожне комп'ютерне підтвердження гіпотези до нових меж, кожне часткове доведення просувають наше розуміння — але нагадують нам, скільки ще залишається відкритим.