Verifica numeri primi
Verifica se un numero fino a 40 cifre è primo. Con scomposizione in fattori primi, divisori, primo precedente e successivo, e tutti i primi in un intervallo.
Come funziona la verifica dei numeri primi
Un numero primo è un numero intero maggiore di 1 con esattamente due divisori: 1 e sé stesso. 2, 3, 5, 7 e 11 sono primi. Un numero con più divisori, come 12 (1, 2, 3, 4, 6, 12), è composto. 0 e 1 non sono né primi né composti. Ogni numero intero maggiore di 1 si può scrivere in un solo modo come prodotto di primi, per esempio 360 = 2³ × 3² × 5.
Per verificare n, lo si divide per ogni primo fino a √n. Se n = a × b, uno dei due deve essere √n o più piccolo. Se nessun primo fino a √n divide n, allora n è primo. Per 221, √221 ≈ 14,9 e 221 ÷ 13 = 17, quindi 221 non è primo. Questo calcolatore usa questo metodo per i numeri fino a mille miliardi.
Per numeri più grandi la divisione è troppo lenta, quindi il calcolatore usa il test di Miller-Rabin. Controlla una proprietà che ogni numero primo possiede, con diversi valori di prova chiamati basi. Con i primi 13 numeri primi come basi, il test è dimostrato corretto per ogni numero sotto circa 3,3 × 10²⁴. Oltre si usano 20 basi e il risultato si chiama probabile primo. I numeri composti vengono scomposti con il metodo rho di Pollard.
Avvertenza legale: Questo calcolatore esegue operazioni matematiche standard solo per uso generale ed educativo. Non sostituisce una verifica professionale — per calcoli in cui la precisione è fondamentale, come dichiarazioni finanziarie, lavori di ingegneria o consegne accademiche, verifica il risultato in modo indipendente.
Domande frequenti
Informazioni su questa calcolatrice
Questo strumento di verifica dei numeri primi ti dice subito se un numero intero è primo. Se non lo è, vedi la sua scomposizione in fattori primi e i suoi divisori. Mostra anche il primo precedente e il successivo, segnala i primi gemelli e i primi di Mersenne, e spiega ogni passaggio per i numeri fino a mille miliardi. Nella scheda Primi in un intervallo puoi elencare tutti i primi tra due numeri.
Che cosa rende primo un numero
Un numero primo è un numero intero maggiore di 1 con esattamente due divisori: 1 e sé stesso. 2, 3, 5, 7, 11 e 13 sono i primi numeri primi. 2 è l'unico primo pari, perché ogni altro numero pari è divisibile per 2. Un numero intero maggiore di 1 che non è primo si chiama composto. 0 e 1 non sono né primi né composti.
I numeri primi sono i mattoni di tutti i numeri interi. Il teorema fondamentale dell'aritmetica dice che ogni numero intero maggiore di 1 si scrive in un solo modo come prodotto di primi, senza contare l'ordine. Per esempio, 360 = 2³ × 3² × 5. È questa la scomposizione che lo strumento mostra per i numeri composti.
Come funziona la verifica
Numeri piccoli e medi (fino a mille miliardi): divisione per tentativi. Per verificare n, lo strumento lo divide per ogni primo fino a √n. Basta questo, perché se n = a × b, allora a o b deve essere √n o più piccolo. Se nessuno di questi primi divide n, n è primo. Per 1.000.000.007, √n ≈ 31.623, quindi prova i 3.401 primi fino a 31.622 e vede che nessuno lo divide.
Numeri grandi: il test di Miller-Rabin. Oltre mille miliardi, lo strumento usa il test di Miller-Rabin. Ogni primo dispari p supera un controllo che consiste nello scrivere p − 1 = 2ˢ × d ed elevare un valore di prova (una base) alla potenza d modulo p. Un numero composto fallisce con la maggior parte delle basi. Con i primi 13 numeri primi (da 2 a 41) come basi, il test è dimostrato corretto per ogni numero sotto circa 3,3 × 10²⁴. Per numeri più grandi usa 20 basi e indica il risultato come probabile primo.
Scomposizione: il metodo rho di Pollard. Per scomporre un grande numero composto, lo strumento toglie prima i piccoli fattori primi, poi usa il metodo rho di Pollard, che trova un fattore molto più in fretta della divisione per tentativi. I numeri con fattori primi tutti molto grandi possono richiedere anni di calcolo su qualsiasi computer. In quel caso lo strumento mostra la parte che non è riuscito a scomporre.
Primi in un intervallo: il crivello. La scheda intervallo usa un crivello di Eratostene segmentato. Cancella i multipli di ogni primo fino a √(A), e ogni numero che resta è primo. Così elabora fino a un milione di numeri alla volta, ovunque fino a mille miliardi.
Esempi
- 221: √221 ≈ 14,9, quindi lo strumento prova 2, 3, 5, 7, 11 e 13. 221 ÷ 13 = 17, quindi 221 = 13 × 17 è composto. Molti pensano che 221 sia primo perché è dispari e non finisce per 5.
- 561: 561 = 3 × 11 × 17. È il più piccolo numero di Carmichael, un numero composto che inganna il semplice test di Fermat per ogni base senza fattori in comune con esso. Il test di Miller-Rabin non ha questo punto debole.
- 2.147.483.647: è 2³¹ − 1, un primo di Mersenne e il valore più grande di un intero con segno a 32 bit in programmazione. Lo strumento conferma che è primo e lo segnala come primo di Mersenne.
- 600.851.475.143: = 71 × 839 × 1.471 × 6.857. Il suo fattore primo più grande, 6.857, è la risposta a un noto problema di programmazione (Project Euler, problema 3).
I primi diventano più rari man mano che i numeri crescono, ma non finiscono mai. Il teorema dei numeri primi dice che vicino a un numero n, circa 1 numero ogni ln(n) è primo. Vicino a mille miliardi, ln(10¹²) ≈ 27,6, quindi un blocco di 200.000 numeri dovrebbe contenere circa 7.238 primi. Tra 999.999.800.000 e 1.000.000.000.000 ce ne sono 7.213, e puoi verificarlo con la scheda intervallo.
Dove si usano i numeri primi
- Sicurezza su internet: la cifratura RSA moltiplica due primi segreti di centinaia di cifre ciascuno. Tutti possono vedere il prodotto, ma nessun metodo noto riesce a scomporlo in un tempo ragionevole, ed è questo che protegge la chiave.
- Programmazione: le tabelle hash usano spesso un numero primo di posizioni per distribuire bene i dati, e i problemi delle gare chiedono spesso risultati modulo il primo 1.000.000.007.
- Record matematici: il progetto GIMPS cerca primi di Mersenne molto grandi. Nell'ottobre 2024 ha trovato 2^136.279.841 − 1, un primo con più di 41 milioni di cifre.
- Scuola: trovare i primi, costruire alberi dei fattori e contare i divisori sono argomenti di base, e i passaggi dettagliati mostrano ogni divisione.
- Verifica immediata — Verifica qualsiasi numero intero fino a 40 cifre e dice se è primo, composto o nessuno dei due (0 e 1).
- Scomposizione e divisori — Scompone i numeri composti in fattori primi con esponenti e mostra il numero di divisori e i divisori stessi.
- Passo per passo — Per i numeri fino a mille miliardi, mostra √n, i primi provati e la divisione che dimostra la risposta.
- Primi in un intervallo — Elenca tutti i primi tra due numeri, fino a mille miliardi e un milione di numeri alla volta, con il numero di coppie di primi gemelli.
- Primi vicini e speciali — Mostra il primo precedente e il successivo, e segnala i primi gemelli e i primi di Mersenne.