Prime Number Checker
Verifica se un numero è primo e trova i suoi fattori. Testa istantaneamente qualsiasi numero e trova tutti i fattori primi. Nessuna registrazione necessaria.
Che cos'è un numero primo?
Un numero primo è un numero naturale maggiore di 1 che ha esattamente due fattori distinti: 1 e se stesso. I primi primi sono: 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...
Fatti chiave sui numeri primi:
- 2 è l'unico numero pari primo. Ogni altro numero pari è divisibile per 2, quindi ha più di due fattori.
- 1 non è primo secondo la convenzione moderna. Escludendo 1 si preserva l'unicità della fattorizzazione primaria (Teorema fondamentale dell'aritmetica).
- I numeri primi sono infiniti. Euclide lo dimostrò intorno al 300 a.C.: supponendo una lista finita di tutti i primi p₁, p₂, ..., pₙ. Allora il numero (p₁ × p₂ × ... × pₙ) + 1 è o è primo stesso o ha un fattore primo non nella lista — contraddizione. Quindi la lista è infinita.
- Man mano che i numeri diventano più grandi, i primi diventano meno frequenti — ma non si fermano. Ci sono 25 primi inferiori a 100, 168 inferiori a 1.000 e 78.498 inferiori a 1.000.000.
Un numero composto è qualsiasi intero positivo maggiore di 1 che non è primo — ha almeno un fattore diverso da 1 e se stesso. Il numero 12 è composto perché 12 = 2 × 6 = 3 × 4 = 2 × 2 × 3. Ogni numero composto ha una fattorizzazione primaria unica (Teorema fondamentale dell'aritmetica).
Come verificare se un numero è primo
Esistono diversi metodi per il test di primalità, che vanno dalla semplice divisione per prove alla complessa divisione per prove probabilistiche:
Divisione per prove (metodo base): Verifica se qualsiasi intero da 2 a √n divide n in modo uniforme. Se non lo fa, n è primo. Si deve verificare solo fino a √n perché se n = a × b con a ≤ b, allora a ≤ √n. Se non si trova alcun divisore fino a √n, non ce ne sono sopra √n.
Divisione per prove ottimizzata: Dopo aver verificato la divisibilità per 2, verificare solo i numeri dispari. Inoltre: verificare 2, 3, quindi solo i numeri della forma 6k±1 (poiché tutti i primi > 3 sono di questa forma). Ciò riduce il numero di test di circa il 66% rispetto alla divisione per prove naive.
| Numero | √n (approssimativo) | Test divisori fino a | Primo? |
|---|---|---|---|
| 97 | 9,85 | 2, 3, 5, 7 | Sì (nessuno divide uniformemente) |
| 91 | 9,54 | 2, 3, 5, 7 | No (7 × 13 = 91) |
| 1.009 | 31,76 | Fino a 31 | Sì (primo) |
| 1.001 | 31,64 | Fino a 31 | No (7 × 11 × 13 = 1.001) |
| 7.919 | 88,99 | Fino a 89 | Sì (il 1.000° primo) |
Per grandi numeri (centinaia di cifre), la divisione per prove è computazionalmente inutilizzabile. Vengono utilizzati invece test avanzati come il test di primalità di Miller-Rabin (probabilistico, utilizzato nella crittografia) e il test di primalità AKS (deterministico polinomiale, 2002).
Fattorizzazione Prima
Ogni numero composto può essere scritto come un prodotto unico di primi — la sua fattorizzazione prima. Questo è garantito dal Teorema Fondamentale dell'Aritmetica. Per trovare la fattorizzazione prima, dividere ripetutamente per il fattore primo più piccolo:
| Numero | Fattorizzazione prima | Decomposizione del albero dei fattori |
|---|---|---|
| 12 | 2² × 3 | 12 → 4×3 → 2×2×3 |
| 60 | 2² × 3 × 5 | 60 → 4×15 → 2²×3×5 |
| 100 | 2² × 5² | 100 → 4×25 → 2²×5² |
| 360 | 2³ × 3² × 5 | 360 → 8×45 → 2³×3²×5 |
| 1,024 | 2¹⁰ | Tutti i fattori primi sono 2 |
| 2,310 | 2 × 3 × 5 × 7 × 11 | Prodotto dei primi 5 primi |
La fattorizzazione prima è utilizzata per trovare il massimo comune divisore (MCD) e il minimo comune multiplo (MCM) dei numeri. MCD(12, 18) = 2² × 3? No — prendere il potenza minima dei primi condivisi: MCD = 2¹ × 3¹ = 6. MCM prende la potenza massima: MCM(12, 18) = 2² × 3² = 36.
Perché i Numeri Primi sono Importanti: Applicazioni in Matematica e Tecnologia
I numeri primi sono gli "atomi" dell'aritmetica — il Teorema Fondamentale dell'Aritmetica afferma che ogni intero positivo maggiore di 1 è o primo o può essere espresso come un prodotto unico di primi. Questa unicità rende i numeri primi i blocchi costruttivi irriducibili di tutti i numeri.
La sicurezza moderna della rete dipende dai numeri primi. La crittografia RSA (utilizzata per HTTPS, crittografia degli email e firme digitali) genera chiavi pubbliche moltiplicando due grandi numeri primi p e q per formare n = p × q. Le chiavi di crittografia e decrittografia sono calcolate utilizzando l'algebra modulare con n. La sicurezza si basa sul problema di fattorizzazione intera: dato n (un numero a 2048 bit con ~617 cifre decimali), trovare p e q è computazionalmente inattuabile con la tecnologia attuale.
Scambio di chiavi Diffie-Hellman utilizza grandi moduli primi per un accordo di chiavi sicuro. Quando si connette a un sito web tramite HTTPS, i numeri primi proteggono silenziosamente i dati in tempo reale.
Tabella di hash utilizza array di dimensioni primi per minimizzare le collisioni. Quando una funzione di hash mappa chiavi a indici di cassetto, utilizzando un numero primo di cassetto assicura una distribuzione migliore perché i numeri primi non hanno fattori che potrebbero creare schemi di collisione sistematici.
Generatore di numeri pseudocasuali (PRNG) utilizza moduli primi in generatori lineari congruenti e altri algoritmi. Il periodo (prima della ripetizione) di tali generatori spesso è uguale al modulo primo meno 1.
Tipi Speciali di Numeri Primi
All'interno dell'insieme infinito dei numeri primi, certi sottinsiemi hanno proprietà o significato speciali:
| Tipo | Definizione | Esempi |
|---|---|---|
| Primi gemelli | Primi differenziati da 2 | (3,5), (11,13), (17,19), (41,43) |
| Primi di Mersenne | Primi della forma 2ⁿ − 1 | 3, 7, 31, 127, 8,191 |
| Primi di Fermat | Primi della forma 2^(2ⁿ) + 1 | 3, 5, 17, 257, 65,537 |
| Primi di Sophie Germain | p e 2p+1 sono entrambi primi | 2, 3, 5, 11, 23, 29 |
| Primi palindromici | Primi che leggono la stessa cosa all'indietro e in avanti | 11, 101, 131, 151, 181 |
| Primi sicuri | Primi p dove (p−1)/2 è anche primo | 5, 7, 11, 23, 47, 59 |
Primi di Mersenne (2ⁿ − 1) sono particolarmente importanti perché possono essere testati per la primità utilizzando l'efficiente test di Lucas-Lehmer. Il progetto GIMPS (Great Internet Mersenne Prime Search) sfrutta il calcolo distribuito a livello mondiale per trovare nuovi primi di Mersenne. Fino al 2024, il più grande noto primo di Mersenne è 2^136,279,841 − 1, con oltre 41 milioni di cifre decimali.
Primi gemelli (coppie differenziate da 2) sono congetturati essere infiniti (Congettura dei primi gemelli), ma ciò rimane non provato — uno dei problemi più famosi aperti in matematica. Nel 2013, Yitang Zhang ha provato il risultato più debole che ci siano infinite coppie di primi differenziate da al massimo 70 milioni, che è stato successivamente migliorato a 246.
Distribuzione dei Numeri Primi
I numeri primi diventano meno frequenti man mano che i numeri aumentano di dimensione, ma la loro distribuzione segue modelli statistici descritti dal Teorema dei Numeri Primi:
Il Teorema dei Numeri Primi (prodotto indipendentemente da Hadamard e de la Vallée-Poussin nel 1896) afferma che il numero di primi fino a N, denotato π(N), è approssimativamente N / ln(N) per grandi N:
| N | π(N reale | Approssimativo N/ln(N) | Densità |
|---|---|---|---|
| 100 | 25 | 21,7 | 1 su 4 |
| 1.000 | 168 | 144,8 | 1 su 6 |
| 10.000 | 1.229 | 1.085,7 | 1 su 8 |
| 100.000 | 9.592 | 8.685,9 | 1 su 10 |
| 1.000.000 | 78.498 | 72.382,4 | 1 su 13 |
| 1.000.000.000 | 50.847.534 | 48.254.942 | 1 su 20 |
La Ipotesi di Riemann — uno dei Problemi del Millennio con un premio di 1 milione di dollari — concerne la distribuzione precisa dei numeri primi. Congetture che tutti i zeri non triviali della funzione zeta di Riemann abbiano parte reale 1/2. Questo è collegato a come "casuale" appare la distribuzione dei numeri primi — l'ipotesi prevede regolarità ottimale nei vuoti primi.
Domande frequenti
È un numero primo 1?
No. Con la convenzione matematica moderna, 1 non è né primo né composto. Escludendo 1 dai numeri primi si preserva l'unicità della fattorizzazione primaria (il Teorema fondamentale dell'aritmetica) — se 1 fosse primo, ogni numero avrebbe infiniti fattori (ad esempio, 6 = 2×3 = 1×2×3 = 1×1×2×3 = ...). Storicamente, alcuni matematici consideravano 1 primo, ma la definizione moderna esclude 1.
Qual è il numero primo più grande conosciuto?
Al 2024, il numero primo più grande conosciuto è 2^136,279,841 − 1 (un numero di Mersenne), scoperto nel 2024. Ha oltre 41 milioni di cifre. Il Great Internet Mersenne Prime Search (GIMPS) progetto trova la maggior parte dei record primi utilizzando calcoli distribuiti da volontari in tutto il mondo. Questi enormi numeri primi non hanno applicazioni pratiche — la loro ricerca è puramente di esplorazione matematica.
Esistono pattern nei numeri primi?
I numeri primi appaiono irregolari, ma esistono pattern. Tutti i numeri primi > 5 si concludono con 1, 3, 7 o 9 (mai 0, 2, 4, 5, 6, 8). Tutti i numeri primi > 3 sono della forma 6k±1. I numeri primi gemelli (che differiscono di 2, come 11 e 13) sembrano continuare all'infinito (congettura dei numeri primi gemelli non provata). Il Teorema dei numeri primi descrive la densità statistica dei numeri primi vicino a N come circa 1/ln(N).
È un numero primo 2?
Sì, 2 è un numero primo — e è l'unico numero pari primo. 2 ha esattamente due fattori (1 e 2), soddisfacendo la definizione. Ogni altro numero pari è divisibile per 2, rendendolo composto. La primità di 2 è un caso speciale che spesso deve essere trattato separatamente in algoritmi e prove.
Come viene utilizzata la primità nella crittografia?
RSA crittografia genera una coppia di chiavi scegliendo due numeri primi grandi p e q (ciascuno 1024+ bit), (2) calcolando n = p×q, (3) derivando la chiave di crittografia e la chiave di decrittografia utilizzando l'algebra modulare. Chiunque può crittografare con n e e (chiave pubblica), ma solo il possessore di p e q (o d) può decrittografare. La sicurezza si basa sulla difficoltà computazionale di fattorizzare n in p×q.
Come si controlla velocemente se un numero è primo?
Per piccoli numeri (fino a ~10^12): la divisione trial ottimizzata controlla solo fino a √n utilizzando il pattern 6k±1. Per numeri medi: il test di primità di Miller-Rabin con alcuni testimoni è probabilistico ma estremamente veloce. Per numeri molto grandi (dimensioni crittografiche, 1000+ cifre): test probabilistici come Miller-Rabin con molti testimoni random, o il test AKS per una prova deterministica.
Che cos'è un gap di primi?
Un gap di primi è la differenza tra due numeri primi consecutivi. Il gap di primi più piccolo è 1 (tra 2 e 3), e tutti gli altri numeri primi consecutivi hanno gap di almeno 2 (poiché uno deve essere dispari). I gap crescono lentamente in media: vicino a N, il gap medio tra numeri primi è ln(N). Esistono eccezionalmente grandi gap di primi — ci sono sequenze arbitrarie lunghe di numeri composti consecutivi (n!+2, n!+3, ..., n!+n sono tutti composti per qualsiasi n).
Quali sono i fattori primi di 100?
100 = 2 × 50 = 2 × 2 × 25 = 2 × 2 × 5 × 5 = 2² × 5². I fattori primi di 100 sono 2 e 5. Questa fattorizzazione spiega perché 100 divide uniformemente per 1, 2, 4, 5, 10, 20, 25, 50 e 100 — ogni divisore corrisponde a una combinazione di 2⁰˒¹˒² e 5⁰˒¹˒².
Che cos'è la congettura di Goldbach?
La congettura di Goldbach (1742) afferma che ogni numero pari maggiore di 2 può essere espresso come la somma di due numeri primi. Ad esempio: 4=2+2, 6=3+3, 8=3+5, 10=3+7, 100=3+97=11+89=17+83. È stata verificata computazionalmente fino a 4×10^18 ma rimane non provata. È uno dei problemi più antichi e più famosi non risolti della teoria dei numeri.
Quanti numeri primi ci sono?
Ci sono infiniti numeri primi — Euclide lo dimostrò intorno al 300 a.C. La dimostrazione per contraddizione: se i numeri primi fossero finiti, il loro prodotto più 1 sarebbe o un numero primo o avrebbe un fattore primo non nella lista supposta completa, una contraddizione. Mentre i numeri primi diventano meno densi a numeri più grandi, non si fermano mai. Ci sono esattamente 78,498 numeri primi sotto 1,000,000 e 5,761,455 numeri primi sotto 100,000,000.
Primi in Teoria dei Numeri e Problemi Insoluti
I numeri primi si trovano al centro di alcuni dei problemi più belli e più ostinati della matematica che rimangono insoluti. La comprensione di queste domande aperte illumina quanto sappiamo sui numeri primi — e quanto rimane misterioso nonostante secoli di sforzi.
Ipotesi di Riemann (1859): La funzione zeta di Riemann ζ(s) = Σ(1/nˢ) si collega alla distribuzione dei numeri primi attraverso i suoi zeri. L'ipotesi afferma che tutti i zeri non triviali si trovano sulla linea critica Re(s) = 1/2. Se vera, fornirebbe la descrizione più precisa possibile di come sono distribuiti i numeri primi. Sono stati calcolati oltre 10 trilioni di zeri e tutti si trovano sulla linea critica — ma non esiste una prova. È un problema del millennio con un premio di 1 milione di dollari dall'Istituto di Matematica Clay.
Congettura delle coppie primi gemelle: Ci sono infinitamente molte coppie di numeri primi (p, p+2) — come (11,13), (17,19), (41,43), (101,103)? La congettura dice sì, ma rimane insoluta. Nel 2013, Yitang Zhang ha fatto un passo avanti dimostrando che ci sono infinitamente molte coppie di numeri primi con un divario di al massimo 70 milioni — un primo limite finito. Il Progetto Polymath ha successivamente ridotto questo limite a 246, il che significa che sappiamo che ci sono infinitamente molte coppie di numeri primi con un divario ≤ 246. Il divario di 2 rimane insoluta.
Congettura di Goldbach (1742): Ogni numero pari maggiore di 2 è la somma di due numeri primi. Verificato computazionalmente fino a 4 × 10^18. Ogni numero pari provato fino a ora soddisfa la congettura — spesso in molti modi (100 = 3+97 = 11+89 = 17+83 = 29+71 = 41+59 = 47+53). Tuttavia, non esiste una prova che copra tutti i numeri pari. La "congettura debole di Goldbach" (ogni numero dispari ≥ 7 è la somma di tre numeri primi) è stata dimostrata nel 2013 da Harald Helfgott.
Primi di Mersenne e numeri perfetti: Un numero di Mersenne è di una forma 2ⁿ − 1 (dove n stesso deve essere un numero primo). I primi sono: 3, 7, 31, 127, 8191. Solo 52 sono noti al 2024. I numeri di Mersenne sono collegati ai numeri perfetti: ogni numero di Mersenne genera un numero perfetto pari attraverso la formula 2^(p−1) × (2^p − 1). Il numero 28 = 4 × 7 (utilizzando il numero di Mersenne 7) e 496 = 16 × 31 (utilizzando il numero di Mersenne 31) sono numeri perfetti. Ci sono infinitamente molti numeri di Mersenne? Sconosciuto.
Congettura ABC e le sue implicazioni: La congettura ABC (stata nel 1985) è una profonda relazione sui fattori primi di tre numeri a + b = c. Se provata, implicherebbe il teorema di Fermat e molti altri risultati come corollari facili. Nel 2012, Shinichi Mochizuki ha pubblicato una presunta dimostrazione utilizzando la sua teoria inter-universale di Teichmüller — ma la dimostrazione è così innovativa e complessa che la comunità matematica ha discusso della sua validità per oltre una decade, con alcuni matematici che l'accettano e altri trovano un vuoto.
I numeri primi rimangono il mistero matematico più profondo: semplici da definire (un numero con esattamente due fattori), ma la loro distribuzione è complessa abbastanza da sottostare a problemi aperti che hanno resistito alle menti matematiche più grandi per secoli. Ogni nuovo record di primo scoperto, ogni verifica computazionale di una congettura fino a un nuovo limite e ogni dimostrazione parziale avanzano la nostra comprensione — mentre ci ricordano quanto c'è ancora da scoprire.