Provera prostog broja

Kako se koristi provera prostog broja

1. Upiši Ceo broj. Prihvataju se i izrazi: 2^61-1, 10^12+39, 20!+1 ili 3711.
2. Odgovor se pojavljuje dok kucaš; pritisni Proveri da rastavljanju daš više vremena kod teškog broja.
3. Pročitaj zaključak, Rastavljanje na proste činioce, Broj delilaca, Prethodni prost broj i Sledeći prost broj. Odeljak Zašto objašnjava kako je odgovor dobijen, a Kopiraj faktorizaciju kopira proizvod prostih brojeva.
4. Za spisak prostih brojeva popuni Od i Do u odeljku Prosti brojevi u opsegu i pritisni Navedi proste brojeve.

Prihvataju se brojevi do 2048 bitova (oko 617 cifara), a sve se izvršava u tvom pregledaču. Ništa što upišeš ne šalje se na server.

Šta čini broj prostim

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

Broj delilaca sledi iz faktorizacije: svakom izložiocu dodaj 1 i pomnoži. 360 = 2³ × 3² × 5 ima (3 + 1)(2 + 1)(1 + 1) = 24 delioca. Prost broj uvek ima tačno 2.

Kako funkcioniše provera

• Mali brojevi (ispod milion) proveravaju se probnim deljenjem: ako nijedan prost broj do kvadratnog korena ne deli broj, on je prost. Nema potrebe ići dalje, jer složen broj uvek ima činilac koji nije veći od njegovog kvadratnog korena.
• Veći brojevi se prvo dele svim prostim brojevima manjim od 1000, a zatim prolaze Miler–Rabinov test. Sa 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 cele brojeve. Za te brojeve je odgovor siguran.
• Iznad 3,3 × 10²⁴ koristi se 25 baza, a broj koji prođe sve prijavljuje se kao verovatno prost. Verovatnoća greške je manja od 1 prema 10¹⁵, ali to nije matematički dokaz. Kada test padne, broj je sigurno složen.

Kako se brojevi rastavljaju

Mali činioci se nalaze probnim deljenjem. Veći složeni delovi se razlažu Polardovim rho algoritmom (Brentova varijanta), koji pronalazi činioce do otprilike 10 cifara za delić sekunde. Teži brojevi, kao proizvod dva prosta broja od po 15 i više cifara, mogu trajati mnogo duže od bilo kog vremenskog ograničenja, pa se rastavljanje prekida posle nekoliko sekundi. Poslednji činilac je tada označen kao složen, ali nerastavljen, a ponovni pritisak na Proveri daje mu više vremena.

Prosti brojevi u opsegu

Spisak u opsegu koristi segmentirano Eratostenovo sito, koje precrtava višekratnike svakog prostog broja. Prihvata do 1.000.000 brojeva po opsegu sa gornjom granicom do 10¹². Brojač obuhvata ceo opseg, a navodi se prvih 2000 prostih brojeva. Na primer, između 1 i 100 ima 25 prostih brojeva, a ispod milion ih je 78.498.