Перевірка простих чисел

Прості числа мають рівно два дільники: 1 і самі себе.

Перші прості числа: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29...

Прості числа є «будівельними блоками» для всіх цілих чисел.

Будь-яке ціле число > 1 можна однозначно представити як добуток простих чисел.

Наприклад, 60 = 2² × 3 × 5.

Це фундаментальне поняття в математиці та криптографії.

Щоб перевірити, чи є число n простим, перевірте, чи ділиться воно без залишку на будь-яке ціле число від 2 до квадратного кореня з n; якщо жодне не ділить, то n — просте.

Спершу розберіться з малими числами:

• числа менші за 2 не є простими
• 2 і 3 — прості
• будь-яке парне число більше за 2 є складеним

Потім перевірте непарні дільники до √n, оскільки дільники завжди йдуть парами, менший із яких не може перевищувати квадратний корінь.

Наприклад, для перевірки 97 потрібно протестувати лише 3, 5 та 7 (оскільки √97 ≈ 9.85), і жодне з них не ділить його, тому 97 — просте число. Wolfram MathWorld описує це як метод пробного ділення, найпряміший тест на простоту.

Метод квадратного кореня означає, що вам потрібно перевіряти потенційні дільники лише до √n, а не аж до самого n.

Причина полягає в тому, що якщо n = a × b, то принаймні один із множників a або b має бути меншим або рівним √n; інакше їхній добуток перевищив би n. Отже, якщо нижче √n не знайдено жодного дільника, то більшого дільника теж не існує.

Це значно зменшує обсяг роботи: перевірка того, чи є 9,973 простим числом, вимагає тестування дільників лише приблизно до 99, а не майже до 10 000.

Khan Academy використовує цей аргумент про пари, щоб пояснити, чому пробне ділення зупиняється на квадратному корені, що робить ручну перевірку простих чисел практичною.

Решето Ератосфена знаходить усі прості числа до межі N шляхом багаторазового позначення кратних кожного простого числа як складених.

Почніть зі списку цілих чисел від 2 до N. Візьміть 2, позначте 4, 6, 8, ... як складені; переходьте до наступного непозначеного числа, 3, і позначте 6, 9, 12, ...; продовжуйте з 5, 7 тощо. Числа, які залишаються непозначеними, є простими.

Застосовуючи це до 30, решето залишає 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Назване на честь грецького математика Ератосфена Кіренського, цей алгоритм (задокументований Encyclopaedia Britannica) є одним із найстаріших і найефективніших способів перерахунку простих чисел у діапазоні.

Основна теорема арифметики стверджує, що кожне ціле число, більше за 1, є або простим, або може бути записане як добуток простих чисел єдиним способом, не враховуючи порядок множників.

Наприклад, 360 = 2³ × 3² × 5, і жодна інша комбінація простих чисел у добутку не дає 360. Ця унікальність є причиною того, чому прості числа називають будівельними блоками цілих чисел.

Згідно з Wolfram MathWorld, ця теорема лежить в основі розкладання на прості множники, обчислення найбільшого спільного дільника та модульної арифметики.

Наш калькулятор використовує її під час розкладання числа на множники, гарантуючи, що отриманий розклад на прості множники є єдино можливим.

Прості числа-близнюки — це пари простих чисел, які відрізняються рівно на 2, наприклад (3, 5), (5, 7), (11, 13), (17, 19) та (29, 31).

Проміжок між послідовними простими числами зазвичай зростає зі збільшенням чисел, хоча прості числа-близнюки продовжують з'являтися. Чи існує нескінченна кількість простих чисел-близнюків — це відома гіпотеза про прості числа-близнюки, яка досі не доведена.

Онлайн-енциклопедія цілочислових послідовностей (OEIS) каталогізує менші елементи пар простих чисел-близнюків у послідовності A001359.

Розуміння проміжків між простими числами допомагає пояснити, чому прості числа стають рідшими: біля одного мільйона прості числа розташовані на середній відстані приблизно 14 одне від одного, тенденція, описана теоремою про прості числа в Цифровій бібліотеці математичних функцій NIST.

Прості числа живлять сучасну криптографію, особливо шифрування RSA, яке захищає онлайн-банкінг, вебсайти HTTPS та цифрові підписи. RSA спирається на той факт, що перемножити два великі прості числа легко, але розкласти добуток назад на ці прості числа обчислювально складно.

Окрім безпеки, прості числа з'являються в:

• визначенні розміру хеш-таблиць (таблиці довжини простих чисел зменшують колізії)
• генерації псевдовипадкових чисел
• кодах, що виправляють помилки
• життєвих циклах цикад, які еволюціонували навколо років із простими числами, щоб уникати хижаків

Britannica зазначає, що розклад на прості множники також спрощує дроби та обчислює найменші спільні кратні. Цей калькулятор підтримує ці завдання, розкладаючи числа на множники та генеруючи прості числа як для проектування алгоритмів, так і для виконання домашніх завдань з математики.

Просте число має рівно два різних додатних дільники: 1 і саме себе, тоді як складене число має більше двох дільників.

Наприклад, 13 є простим (дільники 1 і 13), а 12 є складеним (дільники 1, 2, 3, 4, 6, 12). Число 1 не є ні простим, ні складеним, оскільки має лише один дільник.

Ця угода зберігає основну теорему арифметики чистою: якби 1 вважалося простим, факторизація більше не була б унікальною, оскільки ви могли б вставити будь-яку кількість одиниць.

Encyclopaedia Britannica та Khan Academy підкреслюють цю відмінність, і саме тому наш інструмент позначає 1 окремо від простих і складених чисел.

Прості числа Мерсенна — це прості числа вигляду 2^p − 1, де показник степеня p є простим числом; прикладами є 3 (2² − 1), 7 (2³ − 1), 31 (2⁵ − 1) та 127 (2⁷ − 1).

Однак не кожен простий показник дає просте число: 2¹¹ − 1 = 2047 = 23 × 89 є складеним.

Прості числа Мерсенна важливі тим, що швидкий тест, який називається тестом Лукаса-Лемера, робить їх легшими для перевірки, ніж довільні числа, тому найбільші відомі прості числа майже завжди є числами Мерсенна з десятками мільйонів цифр.

Великий інтернет-пошук простих чисел Мерсенна (GIMPS) координує волонтерів для їх відкриття. Послідовність OEIS A000668 перелічує відомі прості числа Мерсенна.

• Найпоширеніша помилка полягає в тому, щоб вважати 1 простим числом; воно таким не є, оскільки просте число повинно мати рівно два дільники.
• Інша помилка полягає у забуванні того, що 2 є єдиним парним простим числом, через що люди помилково пропускають його або хибно припускають, що інші парні числа можуть бути простими.
• Третя помилка полягає в тому, щоб зупинити пробне ділення занадто рано або занадто пізно: ви повинні перевірити всі дільники до √n, а не лише кілька малих.
• Люди також плутають розклад на прості множники з перерахунком усіх дільників; число 12 має дільники 1, 2, 3, 4, 6, 12, але розклад на прості множники лише 2² × 3.
• Нарешті, припущення, що кожне число вигляду 6k ± 1 є простим, є хибним; 25 = 6(4) + 1 є складеним.