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

Как се използва проверката за просто число

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.