Prímszám-ellenőrző

A prímszám-ellenőrző használata

1. Írj be egy Egész számot. Kifejezések is elfogadottak: 2^61-1, 10^12+39, 20!+1 vagy 3711.
2. A válasz gépelés közben megjelenik; nehéz számnál nyomd meg az Ellenőrzés gombot, hogy a felbontás több időt kapjon.
3. Olvasd le az eredményt, a Prímtényezős felbontást, az Osztók száma értékét, az Előző prímszámot és a Következő prímszámot. A Miért? panel elmagyarázza, hogyan jutott az eszköz a válaszhoz, a Felbontás másolása pedig a prímek szorzatát másolja a vágólapra.
4. Prímek listázásához töltsd ki az Ettől és az Eddig mezőt a Prímszámok egy tartományban részben, majd nyomd meg a Prímszámok listázása gombot.

Legfeljebb 2048 bites (kb. 617 számjegyű) számokat fogad el, és minden a böngésződben fut, a beírt számok nem kerülnek feltöltésre.

Mitől prím egy szám?

A prímszám 1-nél nagyobb egész szám, amelynek csak az 1 és önmaga az osztója: 2, 3, 5, 7, 11, 13… Az a szám, amelynek más osztója is van, összetett, és pontosan egyféleképpen írható fel prímek szorzataként, ez a prímtényezős felbontás (360 = 2³ × 3² × 5). A 0 és az 1 sem nem prím, sem nem összetett, a 2 pedig az egyetlen páros prímszám.

Az osztók száma a felbontásból adódik: adj 1-et minden kitevőhöz, és szorozd össze az eredményeket. A 360 = 2³ × 3² × 5 esetén (3 + 1)(2 + 1)(1 + 1) = 24 osztó van. A prímszámnak mindig pontosan 2 osztója van.

Hogyan működik a teszt?

• A kis számokat (egymillió alatt) próbaosztással ellenőrzi az eszköz: ha a négyzetgyökig egyetlen prím sem osztja a számot, akkor prím. Tovább felesleges menni, mert egy összetett számnak mindig van a négyzetgyökénél nem nagyobb tényezője.
• A nagyobb számokat először elosztja minden 1000 alatti prímmel, majd átviszi a Miller–Rabin-teszten. A 2, 3, 5, …, 41 alapokból álló 13 alappal ez a teszt bizonyítottan pontos minden 3,3 × 10²⁴ alatti számra, ami az összes 64 bites egész számot is magában foglalja. Ezekre a számokra a válasz biztos.
• 3,3 × 10²⁴ fölött 25 alapot használ, és az a szám, amely mindegyiken átmegy, valószínű prímként jelenik meg. A tévedés esélye 1 a 10¹⁵-höz alatt van, de ez nem matematikai bizonyítás. Ha a teszt elbukik, a szám biztosan összetett.

Hogyan bontja tényezőkre a számokat?

A kis tényezőket próbaosztással találja meg. A nagyobb összetett részeket a Pollard-féle rho-algoritmussal (Brent-változat) bontja fel, amely a legfeljebb körülbelül 10 számjegyű tényezőket a másodperc törtrésze alatt megtalálja. A nehezebb számok, például két legalább 15 számjegyű prím szorzata, bármilyen időkorlátnál hosszabb ideig tarthatnak, ezért a felbontás néhány másodperc után leáll. Az utolsó tényezőt ilyenkor összetettként jelöli, de nem bontja fel, és az Ellenőrzés ismételt megnyomása több időt ad neki.

Prímek egy tartományban

A tartománylista szegmentált Eratoszthenész szitáját használja, amely kihúzza az egyes prímek többszöröseit. Tartományonként legfeljebb 1 000 000 számot fogad el, a felső határ legfeljebb 10¹² lehet. A darabszám az egész tartományra vonatkozik, az első 2000 prímet pedig fel is sorolja. Például 1 és 100 között 25 prím van, egymillió alatt pedig 78 498.