Kontrola prvočísla a rozklad na prvočinitele

Ako používať kontrolu prvočísel

1. Zadaj Celé číslo. Prijímajú sa aj výrazy: 2^61-1, 10^12+39, 20!+1 alebo 3711.
2. Odpoveď sa zobrazí počas písania; tlačidlom Skontrolovať dáš rozkladu viac času pri ťažkom čísle.
3. Prečítaj si verdikt, Rozklad na prvočinitele, Počet deliteľov, Predchádzajúce prvočíslo a Ďalšie prvočíslo. Panel Prečo vysvetľuje, ako sa k odpovedi dospelo, a Kopírovať rozklad skopíruje súčin prvočísel.
4. Ak chceš vypísať prvočísla, vyplň Od a Do v časti Prvočísla v intervale a stlač Vypísať prvočísla.

Prijímajú sa čísla do 2048 bitov (asi 617 číslic) a všetko beží v tvojom prehliadači. Nič, čo zadáš, sa neodosiela na server.

Čo robí číslo prvočíslom

Prvočíslo je celé číslo väčšie ako 1, ktorého jedinými deliteľmi sú 1 a ono samo: 2, 3, 5, 7, 11, 13… Číslo s ďalšími deliteľmi je zložené a dá sa práve jediným spôsobom zapísať ako súčin prvočísel, teda ako rozklad na prvočinitele (360 = 2³ × 3² × 5). Čísla 0 a 1 nie sú ani prvočísla, ani zložené čísla a 2 je jediné párne prvočíslo.

Počet deliteľov vyplýva z rozkladu: ku každému exponentu pripočítaj 1 a výsledky vynásob. Číslo 360 = 2³ × 3² × 5 má (3 + 1)(2 + 1)(1 + 1) = 24 deliteľov. Prvočíslo má vždy presne 2.

Ako test funguje

• Malé čísla (menšie než milión) sa kontrolujú skúšobným delením: ak číslo nedelí žiadne prvočíslo do jeho odmocniny, je prvočíslo. Ďalej ísť netreba, pretože zložené číslo má vždy činiteľ, ktorý nie je väčší ako jeho odmocnina.
• Väčšie čísla sa najprv vydelia každým prvočíslom menším než 1000 a potom prejdú Millerovým–Rabinovým testom. S 13 základmi 2, 3, 5, …, 41 je tento test dokázateľne presný pre každé číslo menšie než 3,3 × 10²⁴, čo zahŕňa všetky 64-bitové celé čísla. Pri týchto číslach je odpoveď istá.
• Nad 3,3 × 10²⁴ sa použije 25 základov a číslo, ktoré prejde všetkými, sa označí ako pravdepodobné prvočíslo. Pravdepodobnosť chyby je menšia než 1 ku 10¹⁵, ale nejde o matematický dôkaz. Ak test zlyhá, číslo je určite zložené.

Ako sa čísla rozkladajú

Malé činitele sa nájdu skúšobným delením. Väčšie zložené časti sa rozkladajú Pollardovým rho algoritmom (Brentov variant), ktorý nájde činitele do približne 10 číslic za zlomok sekundy. Ťažšie čísla, napríklad súčin dvoch prvočísel s 15 a viac číslicami, môžu trvať oveľa dlhšie než akýkoľvek časový limit, preto sa rozklad po niekoľkých sekundách zastaví. Posledný činiteľ sa potom označí ako zložený, ale nerozložený, a opätovné stlačenie Skontrolovať mu dá viac času.

Prvočísla v intervale

Výpis v intervale používa segmentované Eratostenovo sito, ktoré vyškrtáva násobky každého prvočísla. Prijíma až 1 000 000 čísel v intervale s hornou hranicou do 10¹². Počet sa týka celého intervalu a vypíše sa prvých 2 000 prvočísel. Napríklad medzi 1 a 100 je 25 prvočísel a pod milión ich je 78 498.