Provjera prostih brojeva

Kako koristiti provjeru prostih brojeva

1. Upiši Cijeli broj. Prihvaćaju se i izrazi: 2^61-1, 10^12+39, 20!+1 ili 3711.
2. Odgovor se pojavljuje dok tipkaš; pritisni Provjeri da faktorizaciji daš više vremena za težak broj.
3. Pročitaj presudu, Rastav na proste faktore, Broj djelitelja, Prethodni prosti broj i Sljedeći prosti broj. Ploča Zašto objašnjava kako se došlo do odgovora, a Kopiraj rastav kopira umnožak prostih brojeva.
4. Za popis prostih brojeva ispuni Od i Do u odjeljku Prosti brojevi u rasponu i pritisni Ispiši proste brojeve.

Prihvaćaju se brojevi do 2048 bitova (oko 617 znamenki), a sve se izvodi u tvom pregledniku. Ništa što upišeš ne šalje se na poslužitelj.

Što broj čini prostim

Prost broj je cijeli broj veći od 1 čiji su jedini djelitelji 1 i on sam: 2, 3, 5, 7, 11, 13… Broj s drugim djeliteljima je složen i može se na točno jedan način zapisati kao umnožak prostih brojeva, svojim rastavom na proste faktore (360 = 2³ × 3² × 5). Brojevi 0 i 1 nisu ni prosti ni složeni, a 2 je jedini paran prost broj.

Broj djelitelja proizlazi iz rastava: svakom eksponentu dodaj 1 i pomnoži. Broj 360 = 2³ × 3² × 5 ima (3 + 1)(2 + 1)(1 + 1) = 24 djelitelja. Prost broj uvijek ima točno 2.

Kako radi test

• Mali brojevi (manji od milijun) provjeravaju se dijeljenjem: ako nijedan prost broj do korijena ne dijeli broj, on je prost. Nema potrebe ići dalje jer složen broj uvijek ima faktor koji nije veći od njegova korijena.
• Veći brojevi najprije se dijele svakim prostim brojem manjim od 1000, a zatim prolaze Miller–Rabinov test. S 13 baza 2, 3, 5, …, 41 taj je test dokazano točan za svaki broj manji od 3,3 × 10²⁴, što uključuje sve 64-bitne cijele brojeve. Za te je brojeve odgovor siguran.
• Iznad 3,3 × 10²⁴ koristi se 25 baza, a broj koji prođe sve prijavljuje se kao vjerojatno prost. Vjerojatnost pogreške manja je od 1 prema 10¹⁵, ali to nije matematički dokaz. Kad test padne, broj je sigurno složen.

Kako se brojevi faktoriziraju

Mali faktori nalaze se dijeljenjem. Veći složeni dijelovi razlažu se Pollardovim rho algoritmom (Brentova inačica), koji pronalazi faktore do otprilike 10 znamenki za djelić sekunde. Teži brojevi, na primjer umnožak dvaju prostih brojeva od 15 ili više znamenki, mogu trajati puno dulje od bilo kojeg vremenskog ograničenja, pa se faktorizacija nakon nekoliko sekundi zaustavlja. Posljednji faktor tada se označava kao složen, ali ne i razložen, a ponovni pritisak na Provjeri daje mu više vremena.

Prosti brojevi u rasponu

Popis za raspon koristi segmentirano Eratostenovo sito, koje precrtava višekratnike svakog prostog broja. Prihvaća do 1 000 000 brojeva po rasponu s gornjom granicom do 10¹². Broj se odnosi na cijeli raspon, a ispisuje se prvih 2000 prostih brojeva. Na primjer, između 1 i 100 ima 25 prostih brojeva, a ispod milijun njih 78 498.