Калькулятор простих чисел

Просте число — це натуральне число, більше за 1, яке ділиться лише на 1 і на саме себе. Приклади: 2, 3, 5, 7, 11, 13, 17, 19. Число 2 — єдине парне просте число. Числа 4, 6, 9 і 15 не є простими, бо мають інші дільники.

Найпростіший метод — пробне ділення: поділіть число n на всі цілі числа від 2 до √n. Якщо жодне не ділить n без остачі, число просте. Для n=17 перевіряємо дільники до √17 ≈ 4,1 — жодне з 2, 3, 4 не ділить 17, тож 17 — просте. Наш калькулятор використовує саме цей метод.

Найбільше відоме просте число (станом на 2024 рік) — це просте число Мерсенна 2^136 279 841 − 1, відкрите проєктом GIMPS. Воно має понад 41 мільйон цифр. Пошук дедалі більших простих чисел — активна галузь математики й обчислень.

Евклід близько 300 р. до н. е. довів, що простих чисел нескінченно багато. Теорема про розподіл простих чисел стверджує, що кількість простих чисел, менших за n, приблизно дорівнює n / ln(n). До 1 000 є 168 простих чисел; до 1 000 000 — аж 78 498.

Кожне натуральне число, більше за 1, можна однозначно (з точністю до порядку) записати як добуток простих чисел. Наприклад: 12 = 2 × 2 × 3, 30 = 2 × 3 × 5, 100 = 2 × 2 × 5 × 5. Це основна теорема арифметики.

Решето Ератосфена — це давній алгоритм пошуку всіх простих чисел до заданої межі. Почніть із 2 і викресліть усі його кратні; потім перейдіть до наступного невикресленого числа й повторіть. Числа, що залишилися невикресленими, — прості. Метод ефективний для меж до кількох мільйонів.

Ні — 1 не є простим числом. Історично його іноді зараховували до простих, але сучасне визначення його виключає, бо інакше порушилася б основна теорема арифметики (розклади перестали б бути однозначними: напр. 6 = 2×3 = 2×3×1 = 2×3×1×1…).

Прості числа-близнюки — це пари простих чисел, що відрізняються на 2, напр. (3, 5), (11, 13), (17, 19), (29, 31), (41, 43). Гіпотеза про числа-близнюки стверджує, що таких пар нескінченно багато, але вона досі не доведена — це одна з великих відкритих проблем математики.

Прості числа — основа криптографії. Алгоритм RSA спирається на складність розкладу великих чисел на прості множники. Криптографічні ключі довжиною 2048–4096 біт — це добутки двох величезних простих чисел. Без простих чисел безпечний зв’язок в інтернеті був би неможливий.

Калькулятор використовує пробне ділення до √n. Для n = 10^9 = 1 000 000 000 він перевіряє до ~31 623 дільників — це дуже швидко. Для значно більших чисел застосовують імовірнісні тести (Міллера–Рабіна) чи детерміновані (AKS), але для навчальних цілей пробного ділення достатньо.