Provjera prostih brojeva

Kako koristiti provjeru prostih brojeva

1. Upiši Cijeli broj. Prihvataju se i izrazi: 2^61-1, 10^12+39, 20!+1 ili 3711.
2. Odgovor se pojavljuje dok upisuješ; klikni Provjeri da rastavljanju daš više vremena kod teškog broja.
3. Pročitaj odgovor, Rastavljanje na proste faktore, Broj djelilaca, Prethodni prosti broj i Sljedeći prosti broj. Panel Zašto objašnjava kako je dobijen odgovor, a Kopiraj rastavljanje kopira proizvod prostih brojeva.
4. Za ispis prostih brojeva popuni Od i Do u dijelu Prosti brojevi u rasponu i klikni Ispiši proste brojeve.

Prihvataju se brojevi do 2048 bita (oko 617 cifara), a sve radi u tvom pregledniku. Ništa što upišeš ne šalje se na server.

Šta čini broj prostim

Prost broj je cijeli broj veći od 1 čiji su jedini djelioci 1 i on sam: 2, 3, 5, 7, 11, 13… Broj koji ima i druge djelioce je složen, a može se na tačno jedan način zapisati kao proizvod prostih brojeva, tj. svoje faktorizacije (360 = 2³ × 3² × 5). Brojevi 0 i 1 nisu ni prosti ni složeni, a 2 je jedini paran prost broj.

Broj djelilaca slijedi iz faktorizacije: svakom eksponentu dodaj 1 i pomnoži. 360 = 2³ × 3² × 5 ima (3 + 1)(2 + 1)(1 + 1) = 24 djelioca. Prost broj uvijek ima tačno 2.

Kako radi test

• Mali brojevi (manji od milion) provjeravaju se probnim dijeljenjem: ako nijedan prost broj do kvadratnog korijena ne dijeli broj, on je prost. Nema potrebe ići dalje, jer složen broj uvijek ima faktor koji nije veći od njegovog kvadratnog korijena.
• Veći brojevi se prvo dijele svim prostim brojevima manjim od 1000, a zatim prolaze Miller–Rabinov test. S 13 baza 2, 3, 5, …, 41 ovaj test je dokazano tačan za svaki broj manji od 3,3 × 10²⁴, što uključuje sve 64-bitne cijele brojeve. Za te brojeve je odgovor siguran.
• Iznad 3,3 × 10²⁴ koristi se 25 baza, a broj koji prođe sve prikazuje se kao vjerovatno prost. Šansa za grešku je manja od 1 prema 10¹⁵, ali to nije matematički dokaz. Kad test padne, broj je sigurno složen.

Kako se brojevi rastavljaju

Mali faktori se nalaze probnim dijeljenjem. Veći složeni dijelovi razbijaju se Pollardovim rho algoritmom (Brentova varijanta), koji pronalazi faktore do oko 10 cifara za djelić sekunde. Teži brojevi, poput proizvoda dva prosta broja od 15 ili više cifara, mogu trajati mnogo duže od bilo kojeg vremenskog ograničenja, pa se rastavljanje zaustavlja nakon nekoliko sekundi. Posljednji faktor je tada označen kao složen ali nerastavljen, a ponovni klik na Provjeri daje mu više vremena.

Prosti brojevi u rasponu

Ispis raspona koristi segmentirano Eratostenovo sito, koje precrtava višekratnike svakog prostog broja. Prihvata do 1.000.000 brojeva po rasponu s gornjom granicom do 10¹². Brojač obuhvata cijeli raspon, a ispisuje se prvih 2.000 prostih brojeva. Na primjer, između 1 i 100 ima 25 prostih brojeva, a ispod milion ih je 78.498.