Calcolatore di Numeri Primi

Calcolatore di Numeri Primi - Somma, Conteggio e Ricerca dei Primi

🔢 Calcola la somma dei numeri primi, trova i primi in un intervallo, verifica se un numero è primo e trova l’N-esimo primo. Algoritmo veloce del Crivello di Eratostene con visualizzazione.

Cosa sono i numeri primi?

Un numero primo è un numero naturale maggiore di 1 che non può essere ottenuto moltiplicando due numeri naturali più piccoli. In altre parole, ha esattamente due divisori: 1 e sé stesso.

I primi 25 numeri primi

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

Come verificare se un numero è primo

Metodo 1 - Divisione per tentativi:

• Controlla se n è divisibile per un numero da 2 a √n
• Se sì, è composto (non primo)
• Se no, è primo

Esempio: 17 è primo?

• √17 ≈ 4,12, quindi controlliamo la divisibilità per 2, 3, 4
• 17 ÷ 2 = 8,5 (non divisibile)
• 17 ÷ 3 = 5,67 (non divisibile)
• 17 ÷ 4 = 4,25 (non divisibile)
• Risultato: 17 è primo!

Crivello di Eratostene

Antico algoritmo per trovare tutti i primi fino a n:

• Passo 1: Elenca tutti i numeri da 2 a n
• Passo 2: Segna 2 come primo ed elimina tutti i multipli di 2
• Passo 3: Trova il successivo numero non eliminato (3) e segnalo come primo
• Passo 4: Elimina tutti i multipli di quel primo
• Passo 5: Ripeti fino a √n
• Risultato: Tutti i numeri non eliminati sono primi

Somma dei numeri primi

Somma dei primi n numeri primi:

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

Somma dei primi fino a n:

• Fino a 10: 2+3+5+7 = 17
• Fino a 100: somma = 1.060
• Fino a 1000: somma = 76.127

Teorema dei numeri primi

Il numero di primi minori di n è approssimativamente n/ln(n):

• Fino a 100: ~25 primi (reale: 25)
• Fino a 1.000: ~145 primi (reale: 168)
• Fino a 10.000: ~1.086 primi (reale: 1.229)
• Fino a 100.000: ~8.686 primi (reale: 9.592)

Tipi di numeri primi

Primi gemelli: primi che differiscono di 2

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

Primi di Mersenne: della forma 2ᵖ - 1 dove p è primo

• 2² - 1 = 3
• 2³ - 1 = 7
• 2⁵ - 1 = 31
• 2⁷ - 1 = 127
• Il primo più grande conosciuto è di Mersenne (24,8 milioni di cifre!)

Primi di Sophie Germain: primo p tale che 2p+1 sia anch’esso primo

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

Primi di Fermat: della forma 2^(2ⁿ) + 1

• F₀ = 3, F₁ = 5, F₂ = 17, F₃ = 257, F₄ = 65.537
• Sono noti solo 5 primi di Fermat

Applicazioni dei numeri primi

Crittografia (RSA):

• Basata sulla difficoltà di fattorizzare grandi numeri
• Usa due grandi primi (centinaia di cifre)
• Protegge online banking, email e siti web

Tabelle hash:

• Tabelle hash di dimensione prima riducono le collisioni
• Usate in database e caching

Generazione di numeri casuali:

• I primi creano sequenze pseudo-casuali migliori
• Usati in simulazioni e giochi

Fatti interessanti

• Infinità: dimostrata da Euclide ~300 a.C. – i primi non finiscono mai
• Gap: possono essere arbitrariamente grandi
• Congettura di Goldbach: ogni numero pari > 2 è somma di due primi (non dimostrata!)
• Ipotesi di Riemann: premio “da un milione” per una prova sulla distribuzione dei primi
• Distanze tra primi: la differenza tra primi consecutivi tende a crescere
• Probabilità: un numero casuale n ha ~1/ln(n) probabilità di essere primo

Record

• Primo più grande noto: 2^82,589,933 - 1 (scoperto nel 2018, 24.862.048 cifre)
• Primi gemelli più grandi: 2.996.863.034.895 × 2^1.290.000 ± 1
• Calcolo: GIMPS (Great Internet Mersenne Prime Search) progetto distribuito

Fraintendimenti comuni

• 1 NON è primo: per definizione moderna (servono esattamente 2 divisori)
• Non tutti i numeri dispari sono primi: 9, 15, 21, 25... sono composti
• Formula per tutti i primi: non esiste una formula semplice che generi tutti i primi
• Schema nei primi: non esiste uno schema prevedibile (sembrano casuali)

💡 Consiglio: per verificare se un numero grande è primo, basta testare la divisibilità fino alla sua radice quadrata! Ad esempio, per 997 serve testare fino a √997 ≈ 31,6: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31. Se nessuno divide 997 senza resto, allora è primo! Inoltre, tranne 2 e 3, tutti i primi sono della forma 6k±1, e questo può velocizzare ulteriormente la ricerca.