Проверка на прост број

Како се користи проверката на прост број

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¹². Бројот го опфаќа целиот опсег, а се наведуваат првите 2 000 прости броеви. На пример, меѓу 1 и 100 има 25 прости броеви, а под еден милион 78 498.