Ce înseamnă număr prim? Definiție, exemple și lista până la 1000

Un număr prim este un număr natural mai mare decât 1 care are exact doi divizori: 1 și el însuși. Cu alte cuvinte, se împarte fără rest doar la 1 și la el însuși. Primele numere prime sunt 2, 3, 5, 7, 11 și 13. Numerele mai mari decât 1 care au și alți divizori, cum sunt 4, 6 sau 12, se numesc numere compuse.

Ideea se vede cel mai bine cu obiecte, ca în fotografia de mai sus. Poți așeza douăsprezece cuburi într-un dreptunghi de 3 pe 4 sau de 2 pe 6. Cu treisprezece nu reușești: orice formă ai încerca, rămâne un cub pe dinafară, iar singura așezare completă este un rând lung. De aceea 13 e prim, iar 12 nu.

Definiția, pe înțeles

Definiția are două condiții. Numărul trebuie să fie un număr natural mai mare decât 1, iar singurii lui divizori să fie 1 și el însuși. Dacă mai are măcar un divizor, numărul este compus.

• 7 este prim. Se împarte fără rest doar la 1 și la 7.
• 15 este compus. Pe lângă 1 și 15, se împarte la 3 și la 5.
• 2 este prim. Divizorii lui sunt 1 și 2. Este și singurul număr prim par.
• 1 nu este nici prim, nici compus. Are un singur divizor, pe el însuși.

Dreptunghiurile din fotografie spun același lucru în alt limbaj. Dacă un număr se poate așeza într-un dreptunghi cu ambele laturi mai mari decât 1, laturile acelea sunt divizorii lui.

Numerele prime până la 100

Grila de mai jos arată și cum se obține lista. Metoda se numește ciurul lui Eratostene, după Eratostene din Cirene, matematician grec din secolul al III-lea î.Hr. Scrii numerele de la 1 la 100. Îl păstrezi pe 2 și tai toți multiplii lui: 4, 6, 8 și așa mai departe. Treci la primul număr rămas netăiat, 3, și îi tai multiplii. Apoi faci la fel cu 5 și cu 7. Ce rămâne netăiat este prim.

Te poți opri după 7 pentru că 11 × 11 = 121 trece deja de 100. Orice număr compus până la 100 are un divizor mai mic decât 10, deci a fost tăiat înainte.

Ce se vede în listă

• Numerele prime de o cifră, numite și cifre prime, sunt 2, 3, 5 și 7, iar suma lor este 17. Cel mai mic număr prim este 2.
• 2 este singurul prim par, iar 5 singurul care se termină în 5. Toate celelalte se termină în 1, 3, 7 sau 9. Invers nu merge: 21, 27, 39, 49, 51, 57, 63, 69, 77, 81, 87, 91, 93 și 99 se termină la fel și sunt compuse.
• 2 și 3 sunt singurele numere prime consecutive. După ele, din orice două numere vecine unul e par și mai mare decât 2.
• Cel mai mare număr prim de două cifre este 97. De trei cifre, 997.

Numerele prime de la 100 la 200

Sunt 21: 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199.

De ce 1 nu este număr prim

Pentru că 1 are un singur divizor, iar definiția cere exact doi. Regula nu e un moft de manual. Dacă 1 ar fi prim, s-ar strica cea mai utilă proprietate a numerelor prime: fiecare număr se descompune în factori primi într-un singur fel. Azi, 6 = 2 × 3 și atât. Cu 1 printre numerele prime, ai avea și 6 = 1 × 2 × 3, și 6 = 1 × 1 × 2 × 3, fără sfârșit.

Nu s-a gândit toată lumea așa. Matematicianul american Derrick Norman Lehmer îl trecea pe 1 în tabelul de numere prime publicat în 1914, iar liste care începeau cu 1 au mai apărut până în 1956. Convenția de azi s-a impus în secolul XX.

Cum verifici dacă un număr este prim

Împarți numărul la numerele prime, în ordine: 2, 3, 5, 7, 11 și așa mai departe. Dacă vreo împărțire se face fără rest, numărul e compus. Te oprești când pătratul numărului prim încercat trece de numărul tău. Dacă până acolo nicio împărțire nu s-a făcut fără rest, numărul e prim.

De ce te poți opri la rădăcina pătrată

Dacă n este compus, se scrie ca n = a × b. Cei doi factori nu pot fi amândoi mai mari decât √n, pentru că atunci produsul lor ar trece de n. Deci cel puțin unul este cel mult √n, și l-ai fi găsit deja. La un pătrat perfect precum 49 = 7 × 7, divizorul cade fix pe √n, de aceea limita se ia inclusiv.

Pentru 97, √97 ≈ 9,8. Ajunge să încerci 2, 3, 5 și 7: patru împărțiri în loc de 95.

Scurtături pentru primele împărțiri

Pentru divizorii mici, criteriile de divizibilitate te scutesc de calcul:

La 2

Ultima cifră este pară.

La 3

Suma cifrelor se împarte la 3. La 111, suma e 3, deci 111 = 3 × 37.

La 5

Ultima cifră este 0 sau 5.

La 7

Nu există un criteriu la fel de comod. Mai repede faci împărțirea.

La 11

Aduni cifrele cu semne alternante, de la dreapta: +, −, +. Dacă rezultatul se împarte la 11, și numărul se împarte. La 209: 9 − 0 + 2 = 11, deci 209 = 11 × 19.

Exemplu lucrat: este 221 prim?

√221 ≈ 14,9, deci încerci numerele prime până la 13.

1. La 2, 3 și 5

   221 e impar, suma cifrelor e 5 și nu se termină în 0 sau 5. Nu se împarte la niciunul.

2. La 7

   221 : 7 = 31, rest 4. Nu merge.

3. La 11

   1 − 2 + 2 = 1. Nu se împarte la 11.

4. La 13

   221 : 13 = 17, fără rest. Deci 221 = 13 × 17 și este compus.

Ține minte 221. Mai apare o dată, mai jos, la cicade.

Numere care par prime, dar nu sunt

Cele mai multe greșeli vin de la numerele impare care nu se termină în 5 și nu se împart vizibil la 3. Merită recunoscute din vedere:

49 = 7 × 7 · 51 = 3 × 17 · 57 = 3 × 19 · 87 = 3 × 29 · 91 = 7 × 13 · 119 = 7 × 17 · 133 = 7 × 19 · 143 = 11 × 13 · 161 = 7 × 23 · 169 = 13 × 13 · 187 = 11 × 17 · 203 = 7 × 29 · 209 = 11 × 19 · 221 = 13 × 17

Păcălește și matematicienii mari. Se povestește că Alexander Grothendieck, unul dintre cei mai importanți matematicieni ai secolului XX, a dat odată 57 ca exemplu de număr prim. De atunci, în glumă, 57 e cunoscut drept „numărul prim al lui Grothendieck”.

Algoritmul de la informatică

La informatică, testul de primalitate e de obicei primul algoritm adevărat pe care îl scrii. Varianta clasică în C++ tratează separat numerele pare, apoi încearcă doar divizori impari, până la √n:

bool prim(long long n) {
  if (n < 2) return false;
  if (n % 2 == 0) return n == 2;
  for (long long d=3; d*d<=n; d+=2)
    if (n % d == 0) return false;
  return true;
}

Condiția d*d<=n înseamnă același lucru ca d ≤ √n, dar evită funcția sqrt și erorile ei de rotunjire. Pentru numerele cu sute de cifre din criptografie nici asta nu mai ajunge. Acolo se folosesc teste probabiliste, cum e Miller-Rabin, care dau răspunsul în fracțiuni de secundă.

Descompunerea în factori primi

Orice număr natural mai mare decât 1 se scrie ca produs de numere prime, într-un singur fel dacă nu ții cont de ordinea factorilor. Rezultatul se numește teorema fundamentală a aritmeticii și e motivul pentru care numerele prime sunt comparate cu atomii: toate celelalte numere se construiesc din ele.

La școală, descompunerea se scrie pe două coloane. Împarți la cel mai mic număr prim care merge și continui cu câtul, până ajungi la 1:

Citești coloana din dreapta: 360 = 2³ × 3² × 5.

Din forma asta afli repede lucruri care altfel cer mult calcul. Numărul de divizori se obține adunând 1 la fiecare exponent și înmulțind rezultatele: (3 + 1) × (2 + 1) × (1 + 1) = 24. Atâția divizori are 360. Tot din descompuneri se calculează c.m.m.d.c. și c.m.m.m.c., explicat pas cu pas în articolul despre multiplii unui număr.

De ce numerele prime nu se termină niciodată

Pentru că orice listă finită de numere prime ratează măcar unul. Demonstrația apare în Elementele lui Euclid (cartea a IX-a, propoziția 20), scrise pe la anul 300 î.Hr., și încape în patru pași:

1. Presupui că ai lista completă

   Înmulțești toate numerele prime din ea.

2. Aduni 1

   Numărul obținut, să-i spunem N, dă restul 1 la împărțirea cu fiecare prim din listă.

3. Te uiți la factorii lui N

   N are cel puțin un factor prim, poate chiar pe el însuși. Acel factor nu e în listă, pentru că niciun număr din listă nu îl împarte fără rest pe N.

4. Lista nu era completă

   Oricât ai lungi-o, argumentul se repetă.

Un detaliu care încurcă mulți elevi: N nu este neapărat prim. 2 × 3 × 5 × 7 + 1 = 211 este prim, dar 2 × 3 × 5 × 7 × 11 × 13 + 1 = 30 031 = 59 × 509. Demonstrația promite doar că factorii lui N sunt numere prime noi, și aici chiar sunt: nici 59, nici 509 nu erau în listă.

Cât de des apar numerele prime

Tot mai rar. Printre numerele până la 100, unul din patru e prim. Până la un miliard, cam unul din douăzeci.

Rărirea e surprinzător de regulată. În jurul unui număr n, distanța medie dintre două numere prime vecine este aproximativ ln n, logaritmul natural al lui n: în jur de 5 pe la 100 și în jur de 21 pe la un miliard. Asta spune teorema numerelor prime, demonstrată în 1896, independent, de Jacques Hadamard și Charles-Jean de la Vallée Poussin.

Media ascunde însă salturi mari. După 113 urmează treisprezece numere compuse la rând, până la 127. Iar golurile pot fi oricât de lungi. Numărul 1001! este produsul 1 × 2 × 3 × … × 1001. Numerele 1001! + 2, 1001! + 3, până la 1001! + 1001, sunt toate compuse, pentru că fiecare se împarte la numărul adunat. Ai astfel o mie de numere la rând fără niciun prim.

Spirala lui Ulam

În 1963, matematicianul Stanisław Ulam asculta la o conferință o lucrare „lungă și foarte plictisitoare”, după cum avea să povestească Martin Gardner. Ca să treacă timpul, a scris numerele pe o foaie în spirală, pornind din centru, și a marcat numerele prime. Au ieșit la iveală diagonale care nu aveau ce căuta într-un șir aparent întâmplător. Desenul a ajuns în martie 1964 pe coperta revistei Scientific American.

Familii de numere prime

Unele numere prime au primit nume, pentru că au o formă aparte sau pentru că apar în probleme celebre:

Prime gemene

Perechi aflate la distanță 2: (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43). Cea mai mare pereche cunoscută are 388 342 de cifre. Nimeni nu știe dacă există infinit de multe.

Prime Mersenne

De forma 2^p − 1, cu p prim: 3, 7, 31, 127. Nu merge pentru orice p: 2¹¹ − 1 = 2 047 = 23 × 89. Aproape toate recordurile sunt de acest tip, pentru că pentru ele există un test deosebit de rapid, testul Lucas-Lehmer.

Prime Fermat

De forma 2^2k + 1. Se cunosc doar cinci: 3, 5, 17, 257 și 65 537. În 1796, la 18 ani, Carl Friedrich Gauss a arătat că un poligon regulat cu 17 laturi se poate construi cu rigla și compasul, iar motivul ține tocmai de faptul că 17 este prim Fermat. 65 537 este exponentul folosit implicit în cheile RSA.

Prime Sophie Germain

Numere prime p pentru care și 2p + 1 este prim: 2, 3, 5, 11, 23, 29, 41, 53, 83, 89. Poartă numele matematicienei franceze care, pe la 1800, își trimitea lucrările sub numele unui bărbat, Monsieur LeBlanc, ca să fie luate în serios.

Prime palindromice

Se citesc la fel în ambele sensuri: 11, 101, 131, 151, 181, 191, 313, 353, 373, 383. Un palindrom cu număr par de cifre se împarte mereu la 11, așa că 11 este singurul prim palindromic cu număr par de cifre.

Ce nu știe încă nimeni despre numerele prime

Unele dintre cele mai vechi probleme deschise din matematică se pot explica unui copil de zece ani. Rezolvarea lor, nu.

Conjectura lui Goldbach (1742)

Orice număr par mai mare decât 2 este suma a două numere prime: 4 = 2 + 2, 20 = 7 + 13, 100 = 47 + 53. A fost verificată pe calculator pentru toate numerele pare până la 4 × 10¹⁸ de echipa lui Tomás Oliveira e Silva, în 2012. Demonstrația lipsește.

Conjectura primelor gemene

Există infinit de multe perechi de prime gemene? În 2013, Yitang Zhang a demonstrat că există infinit de multe perechi de numere prime aflate la o distanță mai mică de 70 de milioane. Într-un an, munca lui James Maynard și a proiectului colectiv Polymath a coborât pragul la 246. De la 246 la 2 drumul e încă deschis.

Ipoteza lui Riemann (1859)

Leagă poziția numerelor prime de zerourile unei funcții, funcția zeta. Dacă ar fi adevărată, am ști cu mare precizie cât de mult se pot abate numerele prime de la media dată de teorema numerelor prime. Institutul Clay oferă din 2000 un milion de dolari pentru demonstrație.

Cum îți protejează numerele prime datele

Una dintre metodele clasice de criptare cu cheie publică, RSA (după Ron Rivest, Adi Shamir și Leonard Adleman, care au publicat-o în 1977), se sprijină pe o asimetrie simplă. Să înmulțești două numere prime e ușor. Să le găsești pornind de la produs e foarte greu.

La scară mică pare un joc. 61 × 53 = 3 233 calculezi într-o secundă. Invers, dacă primești 3 233 și trebuie să afli din ce numere prime s-a obținut, încerci împărțiri una după alta, până dai de 53. Pentru un număr de patru cifre durează un minut. O cheie RSA obișnuită, de 2 048 de biți, are însă 617 cifre, iar pentru produse de mărimea asta nicio metodă cunoscută nu termină în timp util.

RSA-129, 129 de cifre

Factorizat în aprilie 1994, cu circa 1 600 de calculatoare ale unor 600 de voluntari.

RSA-250, 250 de cifre

Factorizat în februarie 2020, după circa 2 700 de ani de calcul pe un singur nucleu de procesor, împărțiți pe mii de mașini.

RSA-260, 260 de cifre

Factorizat în septembrie 2026, cu circa 4 900 de zile de calcul pe plăci grafice.

Cheie RSA de 2 048 de biți, 617 cifre

Nefactorizată. Estimarea este de circa 10 miliarde de ori mai grea decât RSA-260.

RSA-129 a fost publicat ca provocare în 1977, în Scientific American. Celelalte fac parte dintr-o listă lansată de firma RSA Laboratories în 1991. RSA-260 e vestea proaspătă: a fost factorizat pe 3 septembrie 2026, după 35 de ani în care nu reușise nimeni. Asta nu slăbește cheile de azi: de la 260 la 617 cifre, efortul nu crește de două ori, ci de miliarde de ori.

Numerele prime nu apar doar în RSA. Conexiunile HTTPS folosesc tot mai des curbe eliptice, iar acolo calculele se fac „modulo” un număr prim uriaș. Curba eliptică Curve25519, de pildă, își trage numele din numărul prim 2²⁵⁵ − 19. Semnăturile din Bitcoin folosesc tot o curbă eliptică definită printr-un număr prim.

Amenințarea reală vine din altă parte. Un calculator cuantic destul de mare ar putea rula algoritmul lui Shor, care factorizează rapid. Unul atât de mare încât să spargă chei reale nu s-a construit încă, dar institutul american de standarde NIST a publicat deja, în august 2024, primele standarde de criptografie post-cuantică, care nu se mai bazează pe dificultatea factorizării.

Cel mai mare număr prim cunoscut

Este 2^{136 279 841} − 1, un prim Mersenne cu 41 024 320 de cifre. L-a găsit Luke Durant pe 12 octombrie 2024, cu o rețea de mii de plăci grafice închiriate în cloud, în 24 de centre de date din 17 țări. Are cu peste 16 milioane de cifre mai mult decât recordul anterior, din 2018. La 28 septembrie 2026 era încă primul în clasamentul The Prime Pages.

Ca să-ți faci o idee: tipărit cu 5 000 de cifre pe pagină, numărul ar umple peste 8 200 de pagini. Stivuite, foile ar face un teanc de peste 80 de centimetri.

Căutarea e deschisă oricui. Proiectul GIMPS (Great Internet Mersenne Prime Search) împarte din 1996 munca între calculatoarele voluntarilor și a găsit ultimele 18 numere prime Mersenne. Organizația americană Electronic Frontier Foundation oferă 150 000 de dolari pentru primul număr prim cunoscut cu cel puțin 100 de milioane de cifre. Premiul n-a fost încă revendicat.

Cicadele care numără în ani primi

În estul Statelor Unite trăiesc cicade din genul Magicicada care stau 13 sau 17 ani sub pământ, ca larve, apoi ies toate deodată, cu milioanele, în aceeași primăvară. Ambele durate sunt numere prime. Biologii au două explicații principale, susținute de modele matematice, dar nedemonstrate definitiv.

Prima explicație ține de prădători. Un prădător cu ciclul de 3 ani se întâlnește cu o cicadă de 17 ani abia o dată la 51 de ani. Dacă cicada ar ieși la fiecare 12 ani, orice prădător cu ciclul de 2, 3, 4 sau 6 ani ar prinde-o la fiecare apariție. A doua explicație: ciclurile prime se suprapun rar între ele, deci populațiile de 13 și de 17 ani se amestecă greu.

Un anumit grup de 13 ani și unul de 17 ani, din aceeași zonă, ies în același an doar o dată la 13 × 17 = 221 de ani. Da, același 221 din exemplul de mai sus. S-a întâmplat în 2024, în Illinois, cu grupurile numite Brood XIX (13 ani) și Brood XIII (17 ani), pentru prima dată din 1803. Data viitoare va fi în 2245.

Întrebări frecvente