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

Як користуватися перевіркою простих чисел

1. Введіть Ціле число. Вирази теж приймаються: 2^61-1, 10^12+39, 20!+1 або 3711.
2. Відповідь з’являється під час введення; натисніть Перевірити, щоб дати розкладанню більше часу для складного числа.
3. Прочитайте вердикт, Розклад на прості множники, Кількість дільників, Попереднє просте число і Наступне просте число. Панель Чому пояснює, як отримано відповідь, а Копіювати розклад копіює добуток простих чисел.
4. Щоб отримати список простих чисел, заповніть Від і До в розділі Прості числа в діапазоні та натисніть Показати прості числа.

Приймаються числа до 2048 біт (приблизно 617 цифр), і все працює у вашому браузері: нічого з того, що ви вводите, не надсилається на сервер.

Що робить число простим

Просте число – це ціле число, більше за 1, єдині дільники якого – 1 і воно саме: 2, 3, 5, 7, 11, 13… Число з іншими дільниками називається складеним, і його можна єдиним способом записати як добуток простих чисел – це розклад на прості множники (360 = 2³ × 3² × 5). Числа 0 і 1 не є ні простими, ні складеними, а 2 – єдине парне просте число.

Кількість дільників випливає з розкладу: додайте 1 до кожного показника степеня й перемножте. Число 360 = 2³ × 3² × 5 має (3 + 1)(2 + 1)(1 + 1) = 24 дільники. Просте число завжди має рівно 2 дільники.

Як працює перевірка

• Малі числа (менші за мільйон) перевіряються пробним діленням: якщо жодне просте число до квадратного кореня не ділить число, воно просте. Далі йти не потрібно, бо складене число завжди має множник, не більший за свій квадратний корінь.
• Більші числа спершу діляться на кожне просте число менше за 1000, а потім проходять тест Міллера–Рабіна. З 13 основами 2, 3, 5, …, 41 цей тест доведено точний для кожного числа менше за 3,3 × 10²⁴, що охоплює всі 64-бітні цілі. Для таких чисел відповідь певна.
• Понад 3,3 × 10²⁴ використовується 25 основ, і число, яке пройшло їх усі, подається як ймовірно просте. Імовірність помилки менша за 1 до 10¹⁵, але це не математичний доказ. Якщо тест не пройдено, число напевно складене.

Як розкладаються числа

Малі множники знаходяться пробним діленням. Більші складені частини розкладаються алгоритмом ρ Полларда (варіант Брента), який знаходить множники до приблизно 10 цифр за частку секунди. Складніші числа, наприклад добуток двох простих по 15 цифр і більше, можуть вимагати значно довшого часу, ніж будь-який ліміт, тому розкладання зупиняється за кілька секунд. Тоді останній множник позначається як складений, але нерозкладений, а повторне натискання Перевірити дає йому більше часу.

Прості числа в діапазоні

Список для діапазону використовує сегментоване решето Ератосфена, яке викреслює кратні кожного простого числа. Воно приймає до 1 000 000 чисел у діапазоні з верхньою межею до 10¹². Кількість стосується всього діапазону, а показано перші 2000 простих чисел. Наприклад, між 1 і 100 є 25 простих чисел, а менше за мільйон – 78 498.