Verificare număr prim

Cum folosești verificatorul de numere prime

1. Scrie un Număr întreg. Se acceptă și expresii: 2^61-1, 10^12+39, 20!+1 sau 3711.
2. Răspunsul apare pe măsură ce scrii; apasă Verifică ca să dai descompunerii mai mult timp pentru un număr dificil.
3. Citește verdictul, Descompunere în factori primi, Numărul de divizori, Numărul prim anterior și Următorul număr prim. Panoul De ce explică cum s-a ajuns la răspuns, iar Copiază descompunerea copiază produsul de numere prime.
4. Ca să listezi numere prime, completează De la și Până la sub Numere prime într-un interval și apasă Listează numerele prime.

Sunt acceptate numere de până la 2048 de biți (aproximativ 617 cifre), iar totul rulează în browserul tău.

Ce face ca un număr să fie prim

Un număr prim este un număr întreg mai mare decât 1 ai cărui unici divizori sunt 1 și el însuși: 2, 3, 5, 7, 11, 13… Un număr cu alți divizori este compus și poate fi scris într-un singur mod ca produs de numere prime, descompunerea în factori primi (360 = 2³ × 3² × 5). Numerele 0 și 1 nu sunt nici prime, nici compuse, iar 2 este singurul număr prim par.

Numărul de divizori rezultă din descompunere: adaugi 1 la fiecare exponent și înmulțești. 360 = 2³ × 3² × 5 are (3 + 1)(2 + 1)(1 + 1) = 24 de divizori. Un număr prim are întotdeauna exact 2.

Cum funcționează testul

• Numerele mici (sub un milion) se verifică prin împărțiri succesive: dacă niciun număr prim până la rădăcina pătrată nu divide numărul, acesta este prim. Nu e nevoie să mergi mai departe, deoarece un număr compus are mereu un factor care nu depășește rădăcina lui pătrată.
• Numerele mai mari se împart mai întâi la fiecare număr prim sub 1000, apoi sunt supuse testului Miller–Rabin. Cu cele 13 baze 2, 3, 5, …, 41, acest test este demonstrat exact pentru orice număr sub 3,3 × 10²⁴, ceea ce include toate numerele întregi pe 64 de biți. Pentru ele răspunsul este sigur.
• Peste 3,3 × 10²⁴ se folosesc 25 de baze, iar un număr care le trece pe toate este raportat ca probabil număr prim. Șansa de eroare este sub 1 la 10¹⁵, dar nu este o demonstrație matematică. Când testul eșuează, numărul este cu siguranță compus.

Cum se descompun numerele

Factorii mici se găsesc prin împărțiri succesive. Părțile compuse mai mari se descompun cu algoritmul rho al lui Pollard (varianta lui Brent), care găsește factori de până la aproximativ 10 cifre într-o fracțiune de secundă. Numerele mai dificile, cum este produsul a două numere prime de 15 cifre sau mai mult, pot dura mult peste orice limită de timp, așa că descompunerea se oprește după câteva secunde. Ultimul factor este atunci marcat ca fiind compus, dar nedescompus, iar o nouă apăsare pe Verifică îi acordă mai mult timp.

Numere prime într-un interval

Lista dintr-un interval folosește un ciur al lui Eratostene segmentat, care taie multiplii fiecărui număr prim. Acceptă până la 1.000.000 de numere per interval, cu limita superioară de până la 10¹². Numărul total acoperă tot intervalul, iar primele 2.000 de numere prime sunt listate. De exemplu, între 1 și 100 există 25 de numere prime, iar sub un milion sunt 78.498.