Preverjanje praštevil

Kako uporabljati preverjanje praštevil

1. Vpiši Celo število. Sprejeti so tudi izrazi: 2^61-1, 10^12+39, 20!+1 ali 3711.
2. Odgovor se prikaže med vnašanjem; pri težkem številu s tipko Preveri razcepu daš več časa.
3. Preberi razsodbo, Razcep na prafaktorje, Število deliteljev, Prejšnje praštevilo in Naslednje praštevilo. Plošča Zakaj razloži, kako je orodje prišlo do odgovora, Kopiraj razcep pa skopira zmnožek praštevil.
4. Za izpis praštevil izpolni polji Od in Do pod naslovom Praštevila v območju ter pritisni Izpiši praštevila.

Sprejeta so števila do 2048 bitov (približno 617 števk), vse pa teče v tvojem brskalniku. Nič, kar vneseš, se ne pošlje na strežnik.

Kaj naredi število praštevilo

Praštevilo je celo število, večje od 1, ki ima samo dva delitelja: 1 in samega sebe. Primeri: 2, 3, 5, 7, 11, 13 … Število z drugimi delitelji je sestavljeno in ga je mogoče na natanko en način zapisati kot zmnožek praštevil, kar imenujemo razcep na prafaktorje (360 = 2³ × 3² × 5). Števili 0 in 1 nista ne praštevili ne sestavljeni števili, 2 pa je edino sodo praštevilo.

Število deliteljev izhaja iz razcepa: vsakemu eksponentu prištej 1 in zmnoži. 360 = 2³ × 3² × 5 ima (3 + 1)(2 + 1)(1 + 1) = 24 deliteljev. Praštevilo jih ima vedno natanko 2.

Kako deluje preizkus

• Majhna števila (pod milijon) se preverijo s poskusnim deljenjem: če nobeno praštevilo do kvadratnega korena števila ne deli, je število praštevilo. Dlje ni treba iskati, ker ima sestavljeno število vedno faktor, ki ni večji od njegovega kvadratnega korena.
• Večja števila se najprej delijo z vsemi praštevili pod 1000, nato pa gredo skozi test Miller–Rabin. S 13 bazami 2, 3, 5, …, 41 je bilo dokazano, da je ta test natančen za vsa števila pod 3,3 × 10²⁴, kar vključuje vsa 64-bitna cela števila. Za ta števila je odgovor gotov.
• Nad 3,3 × 10²⁴ se uporabi 25 baz, število, ki jih prestane vse, pa je prikazano kot verjetno praštevilo. Verjetnost napake je manjša od 1 proti 10¹⁵, vendar to ni matematični dokaz. Če test pade, je število zagotovo sestavljeno.

Kako se števila razcepljajo

Majhni faktorji se najdejo s poskusnim deljenjem. Večji sestavljeni deli se razcepijo z Pollardovim algoritmom rho (Brentova različica), ki faktorje do približno 10 števk najde v delčku sekunde. Težja števila, na primer zmnožek dveh praštevil s 15 ali več števkami, lahko zahtevajo veliko več časa od katere koli časovne omejitve, zato se razcep po nekaj sekundah ustavi. Zadnji faktor je tedaj označen kot sestavljen, vendar nerazcepljen, ponoven pritisk na Preveri pa mu da več časa.

Praštevila v območju

Izpis območja uporablja segmentirano Eratostenovo sito, ki prečrta večkratnike vsakega praštevila. Sprejme do 1 000 000 števil na območje z zgornjo mejo do 10¹². Štetje zajame celotno območje, izpisanih je prvih 2000 praštevil. Na primer, med 1 in 100 je 25 praštevil, pod milijonom pa 78 498.