Prvočísla – test prvočíselnosti

Jak používat test prvočíselnosti

1. Do pole Celé číslo napiš číslo. Přijímají se i výrazy: 2^61-1, 10^12+39, 20!+1 nebo 3711.
2. Odpověď se zobrazuje průběžně, jak píšeš; stiskem Zkontrolovat dáš rozkladu těžkého čísla víc času.
3. Přečti si verdikt, Rozklad na prvočinitele, Počet dělitelů, Předchozí prvočíslo a Další prvočíslo. Panel Proč vysvětluje, jak se k odpovědi došlo, a Kopírovat rozklad zkopíruje součin prvočísel.
4. Chceš-li vypsat prvočísla, vyplň Od a Do v části Prvočísla v intervalu a stiskni Vypsat prvočísla.

Přijímají se čísla do 2048 bitů (asi 617 číslic) a všechno probíhá ve tvém prohlížeči, takže nic, co zadáš, se neodesílá na server.

Co dělá číslo prvočíslem

Prvočíslo je celé číslo větší než 1, které je dělitelné jen jedničkou a samo sebou: 2, 3, 5, 7, 11, 13… Číslo s dalšími děliteli je složené a dá se právě jedním způsobem zapsat jako součin prvočísel, tedy jako svůj rozklad na prvočinitele (360 = 2³ × 3² × 5). Čísla 0 a 1 nejsou ani prvočísla, ani složená čísla, a 2 je jediné sudé prvočíslo.

Počet dělitelů plyne z rozkladu: ke každému exponentu přičti 1 a vynásob. Číslo 360 = 2³ × 3² × 5 má (3 + 1)(2 + 1)(1 + 1) = 24 dělitelů. Prvočíslo má vždy právě 2.

Jak test funguje

• Malá čísla (do jednoho milionu) se ověřují zkusmým dělením: pokud žádné prvočíslo do druhé odmocniny číslo nedělí, je prvočíslem. Dál jít není třeba, protože složené číslo má vždy činitele, který není větší než jeho druhá odmocnina.
• Větší čísla se nejdřív vydělí každým prvočíslem menším než 1000 a poté projdou Millerovým–Rabinovým testem. S 13 základy 2, 3, 5, …, 41 je tento test dokázaně přesný pro každé číslo menší než 3,3 × 10²⁴, což zahrnuje všechna 64bitová celá čísla. Pro ně je odpověď jistá.
• Nad 3,3 × 10²⁴ se použije 25 základů a číslo, které projde všemi, se ohlásí jako pravděpodobné prvočíslo. Pravděpodobnost chyby je menší než 1 ku 10¹⁵, ale matematickým důkazem to není. Pokud test selže, je číslo jistě složené.

Jak se čísla rozkládají

Malí činitelé se hledají zkusmým dělením. Větší složené části se rozdělují Pollardovým rho algoritmem (Brentova varianta), který najde činitele do asi 10 číslic za zlomek sekundy. Těžší čísla, například součin dvou prvočísel o 15 a více číslicích, mohou trvat mnohem déle než jakýkoli časový limit, proto se rozklad po několika sekundách zastaví. Poslední činitel je pak označen jako složený, ale nerozložený, a dalším stiskem Zkontrolovat mu dáš více času.

Prvočísla v intervalu

Výpis v intervalu používá segmentované Eratosthenovo síto, které vyškrtává násobky každého prvočísla. Přijímá až 1 000 000 čísel v intervalu s horní mezí do 10¹². Počet se týká celého intervalu a vypíše se prvních 2 000 prvočísel. Například mezi 1 a 100 je 25 prvočísel a pod jedním milionem jich je 78 498.