Verificator numere prime

Numerele prime au exact doi divizori: 1 și ele însele.

Primele numere prime sunt 2, 3, 5, 7, 11, 13, 17, 19, 23, 29...

Numerele prime stau la baza tuturor numerelor întregi.

Orice număr întreg > 1 poate fi exprimat în mod unic ca produs de numere prime.

De exemplu, 60 = 2² × 3 × 5.

Acest concept este fundamental în matematică și criptografie.

Pentru a verifica dacă un număr n este prim, verifică dacă se împarte exact la vreun număr întreg între 2 și rădăcina pătrată a lui n; dacă nu se împarte la niciunul, n este prim.

În primul rând, analizează cazurile simple:

• numerele mai mici de 2 nu sunt prime
• 2 și 3 sunt prime
• orice număr par mai mare de 2 este compus

Apoi testează divizorii impari până la √n, deoarece divizorii vin întotdeauna în perechi în care factorul mai mic nu poate depăși rădăcina pătrată.

De exemplu, pentru a verifica numărul 97 este nevoie să testezi doar divizorii 3, 5 și 7 (deoarece √97 ≈ 9,85), și niciunul nu îl divide, deci 97 este prim. Wolfram MathWorld descrie acest procedeu drept împărțire prin încercări, cel mai direct test de primalitate.

Metoda rădăcinii pătrate presupune că trebuie să testezi divizorii potențiali doar până la √n, nu până la n.

Explicația este că dacă n = a × b, cel puțin unul dintre factorii a sau b trebuie să fie mai mic sau egal cu √n; altfel, produsul lor ar depăși n. Așadar, dacă nu se găsește niciun factor mai mic sau egal cu √n, nu există niciun factor mai mare.

Acest procedeu reduce considerabil volumul de calcul: verificarea dacă 9.973 este prim necesită testarea divizorilor doar până la aproximativ 99, nu până la aproape 10.000.

Khan Academy folosește această logică a perechilor pentru a explica de ce împărțirea prin încercări se oprește la rădăcina pătrată, făcând practică verificarea manuală a primalității.

Ciurul lui Eratostene găsește toate numerele prime până la o limită N prin marcarea repetată a multiplilor fiecărui număr prim ca fiind compuși.

Începi cu o listă de numere întregi de la 2 la N. Iei numărul 2 și marchezi 4, 6, 8, ... ca fiind compuși; treci la următorul număr nemarcat, 3, și marchezi 6, 9, 12, ...; continui cu 5, 7 și așa mai departe. Numerele care rămân nemarcate sunt prime.

Aplicat până la 30, ciurul lasă 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Numit după matematicianul grec Eratostene din Cyrene, acest algoritm (documentat de Encyclopaedia Britannica) este una dintre cele mai vechi și mai eficiente metode de a genera numerele prime dintr-un interval.

Teorema fundamentală a aritmeticii afirmă că orice număr întreg mai mare decât 1 este fie prim, fie poate fi scris ca un produs de factori primi într-un mod unic, făcând abstracție de ordinea factorilor.

De exemplu, 360 = 2³ × 3² × 5 și nicio altă combinație de numere prime nu dă prin înmulțire 360. Această unicitate este motivul pentru care numerele prime sunt considerate cărămizile de bază ale numerelor întregi.

Conform Wolfram MathWorld, această teoremă stă la baza descompunerii în factori primi, a calculării celui mai mare divizor comun și a aritmeticii modulare.

Calculatorul nostru o utilizează atunci când descompune un număr, garantând că descompunerea în factori primi generată este singura posibilă.

Numerele prime gemene sunt perechi de numere prime a căror diferență este exact 2, cum ar fi (3, 5), (5, 7), (11, 13), (17, 19) și (29, 31).

Distanța dintre numerele prime consecutive crește în general pe măsură ce numerele devin mai mari, deși numerele prime gemene continuă să apară. Existența unei infinități de numere prime gemene constituie celebra Conjectură a numerelor prime gemene, rămasă încă nedemonstrată.

On-Line Encyclopedia of Integer Sequences (OEIS) cataloghează primul termen din perechile de numere prime gemene în șirul A001359.

Înțelegerea distanțelor dintre numere prime explică de ce acestea devin tot mai rare: în jurul valorii de un milion, numerele prime sunt distanțate în medie cu aproximativ 14 unități, o tendință descrisă de Teorema numerelor prime din NIST Digital Library of Mathematical Functions.

Numerele prime stau la baza criptografiei moderne, în special a criptării RSA, care securizează serviciile bancare online, conexiunile HTTPS și semnăturile digitale. RSA se bazează pe faptul că înmulțirea a două numere prime mari este facilă, dar descompunerea produsului în factorii săi primi este extrem de dificilă din punct de vedere computațional.

Dincolo de securitate, numerele prime sunt utilizate în:

• dimensionarea tabelelor hash (dimensiunile exprimate în numere prime reduc coliziunile)
• generarea de numere pseudo-aleatorii
• coduri de corectare a erorilor
• ciclurile de viață ale cicadelor, care au evoluat pe durate de ani corespunzătoare unor numere prime pentru a evita prădătorii

Britannica menționează că descompunerea în factori primi simplifică și fracțiile și ajută la calculul celui mai mic multiplu comun. Acest calculator sprijină aceste operațiuni prin descompunerea numerelor și generarea de numere prime, util atât pentru dezvoltarea algoritmilor, cât și pentru temele la matematică.

Un număr prim are exact doi divizori pozitivi diferiți, pe 1 și pe el însuși, în timp ce un număr compus are mai mult de doi divizori.

De exemplu, 13 este prim (divizorii săi sunt 1 și 13), iar 12 este compus (divizorii sunt 1, 2, 3, 4, 6, 12). Numărul 1 nu este nici prim, nici compus, deoarece are un singur divizor.

Această convenție păstrează claritatea Teoremei fundamentale a aritmeticii: dacă 1 ar fi considerat prim, descompunerea în factori nu ar mai fi unică, întrucât s-ar putea adăuga un număr arbitrar de factori egali cu 1.

Encyclopaedia Britannica și Khan Academy evidențiază această distincție, motiv pentru care instrumentul nostru clasifică numărul 1 separat de numerele prime și de cele compuse.

Numerele prime Mersenne sunt numere prime de forma 2^p − 1, unde exponentul p este la rândul său prim; exemple comune sunt 3 (2² − 1), 7 (2³ − 1), 31 (2⁵ − 1) și 127 (2⁷ − 1).

Totuși, nu orice exponent prim generează un număr prim: 2¹¹ − 1 = 2047 = 23 × 89 este compus.

Numerele prime Mersenne au o importanță deosebită deoarece un algoritm rapid, numit testul Lucas-Lehmer, permite verificarea lor mult mai ușor decât în cazul altor numere mari, motiv pentru care cele mai mari numere prime cunoscute sunt aproape întotdeauna numere prime Mersenne cu zeci de milioane de cifre.

Proiectul Great Internet Mersenne Prime Search (GIMPS) coordonează voluntari pentru a le descoperi. Șirul OEIS A000668 inventariază numerele prime Mersenne cunoscute.

• Cea mai frecventă greșeală este considerarea lui 1 ca fiind prim; acesta nu este prim, deoarece un număr prim trebuie să aibă exact doi divizori.
• O altă eroare este trecerea cu vederea a faptului că 2 este singurul număr prim par, ceea ce duce la omiterea lui sau la presupunerea greșită că și alte numere pare ar putea fi prime.
• O a treia greșeală este oprirea împărțirii prin încercări prea devreme sau prea târziu: este esențial să testezi toți divizorii până la √n, nu doar primii câțiva.
• De asemenea, se confundă descompunerea în factori primi cu enumerarea tuturor divizorilor; 12 are divizorii 1, 2, 3, 4, 6, 12, dar descompunerea sa în factori primi este doar 2² × 3.
• În fine, presupunerea că orice număr de forma 6k ± 1 este prim este falsă; de exemplu, 25 = 6(4) + 1 este compus.