Calculator de Numere Prime

Calculator de Numere Prime - Sumă, Numărare și Căutare de Prime

🔢 Calculează suma numerelor prime, găsește numere prime într-un interval, verifică dacă un număr este prim și găsește al n-lea număr prim. Algoritm rapid cu Ciurul lui Eratostene și vizualizare.

Ce sunt numerele prime?

Un număr prim este un număr natural mai mare decât 1 care nu poate fi obținut prin înmulțirea a două numere naturale mai mici. Cu alte cuvinte, are exact doi divizori: 1 și el însuși.

Primele 25 de numere prime

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

Cum verifici dacă un număr este prim

Metoda 1 - Împărțire prin încercare:

• Verifică dacă n este divizibil cu orice număr de la 2 la √n
• Dacă da, este compus (nu este prim)
• Dacă nu, este prim

Exemplu: 17 este prim?

• √17 ≈ 4,12, deci verificăm divizibilitatea cu 2, 3, 4
• 17 ÷ 2 = 8,5 (nu este divizibil)
• 17 ÷ 3 = 5,67 (nu este divizibil)
• 17 ÷ 4 = 4,25 (nu este divizibil)
• Rezultat: 17 este prim!

Ciurul lui Eratostene

Un algoritm antic pentru a găsi toate numerele prime până la n:

• Pasul 1: Listează toate numerele de la 2 la n
• Pasul 2: Marchează 2 ca prim și elimină toate multiplii lui 2
• Pasul 3: Găsește următorul număr nemarcat (3) și marchează-l ca prim
• Pasul 4: Elimină toți multiplii acelui număr prim
• Pasul 5: Repetă până la √n
• Rezultat: Toate numerele rămase nemarcate sunt prime

Suma numerelor prime

Suma primelor n numere prime:

• Primele 10: 2+3+5+7+11+13+17+19+23+29 = 129
• Primele 100: sumă = 24.133
• Primele 1000: sumă = 3.682.913

Suma numerelor prime până la n:

• Până la 10: 2+3+5+7 = 17
• Până la 100: sumă = 1.060
• Până la 1000: sumă = 76.127

Teorema numerelor prime

Numărul de numere prime mai mici decât n este aproximativ n/ln(n):

• Până la 100: ~25 prime (real: 25)
• Până la 1.000: ~145 prime (real: 168)
• Până la 10.000: ~1.086 prime (real: 1.229)
• Până la 100.000: ~8.686 prime (real: 9.592)

Tipuri de numere prime

Prime gemene: numere prime care diferă cu 2

• (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43)...

Prime Mersenne: de forma 2ᵖ - 1 unde p este prim

• 2² - 1 = 3
• 2³ - 1 = 7
• 2⁵ - 1 = 31
• 2⁷ - 1 = 127
• Cel mai mare număr prim cunoscut este de tip Mersenne (24,8 milioane de cifre!)

Prime Sophie Germain: număr prim p pentru care 2p+1 este, de asemenea, prim

• 2 (2×2+1 = 5), 3 (2×3+1 = 7), 5 (2×5+1 = 11), 11, 23, 29...

Prime Fermat: de forma 2^(2ⁿ) + 1

• F₀ = 3, F₁ = 5, F₂ = 17, F₃ = 257, F₄ = 65.537
• Sunt cunoscute doar 5 numere prime Fermat

Aplicații ale numerelor prime

Criptografie (RSA):

• Bazată pe dificultatea factorizării numerelor mari
• Folosește două numere prime mari (sute de cifre)
• Securizează banking-ul online, email-urile și site-urile web

Tabele hash:

• Dimensiunile prime reduc coliziunile
• Folosite în baze de date și caching

Generare de numere aleatoare:

• Primele pot produce secvențe pseudo-aleatoare mai bune
• Folosite în simulări și jocuri

Fapte interesante despre numerele prime

• Infinitate: demonstrată de Euclid ~300 î.Hr. – primele nu se termină niciodată
• Intervale fără prime: pot fi arbitrar de mari
• Conjectura lui Goldbach: orice număr par > 2 este sumă a două numere prime (nedemonstrată!)
• Ipoteza lui Riemann: problemă celebră despre distribuția primelor
• Diferențe între prime: diferența dintre prime consecutive tinde să crească
• Probabilitate: un număr aleator n are ~1/ln(n) șanse să fie prim

Recorduri

• Cel mai mare număr prim cunoscut: 2^82,589,933 - 1 (descoperit în 2018, 24.862.048 cifre)
• Cel mai mare prime gemene: 2.996.863.034.895 × 2^1.290.000 ± 1
• Calcul: GIMPS (Great Internet Mersenne Prime Search) – proiect distribuit

Concepții greșite frecvente

• 1 NU este prim: conform definiției moderne (trebuie exact 2 divizori)
• Nu toate numerele impare sunt prime: 9, 15, 21, 25... sunt compuse
• Formulă pentru toate primele: nu există o formulă simplă care să genereze toate numerele prime
• Model în prime: nu există un tipar previzibil (par „aleatoare”)

💡 Sfat: când verifici dacă un număr mare este prim, trebuie să testezi divizibilitatea doar până la rădăcina sa pătrată! De exemplu, pentru 997, √997 ≈ 31,6, deci testează doar 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31. Dacă niciunul nu împarte exact 997, atunci este prim! În plus, cu excepția lui 2 și 3, toate primele sunt de forma 6k±1, ceea ce poate accelera și mai mult căutarea.