Verifica dei numeri primi (gratis) — fino a mille cifre, con scomposizione

Stabilisce all'istante se un numero fino a mille cifre sia primo. Strumento gratuito che mostra anche la scomposizione in fattori primi, i numeri primi precedente e successivo, i passaggi delle divisioni successive e il metodo con cui l'esito è stato accertato. Senza registrazione.

I numeri primi minori di mille (168 in tutto)

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	101	103	107	109	113	127	131	137	139	149	151
157	163	167	173	179	181	191	193	197	199	211	223
227	229	233	239	241	251	257	263	269	271	277	281
283	293	307	311	313	317	331	337	347	349	353	359
367	373	379	383	389	397	401	409	419	421	431	433
439	443	449	457	461	463	467	479	487	491	499	503
509	521	523	541	547	557	563	569	571	577	587	593
599	601	607	613	617	619	631	641	643	647	653	659
661	673	677	683	691	701	709	719	727	733	739	743
751	757	761	769	773	787	797	809	811	821	823	827
829	839	853	857	859	863	877	881	883	887	907	911
919	929	937	941	947	953	967	971	977	983	991	997

Tutti gli altri numeri minori di mille sono composti e hanno almeno un divisore diverso da uno e da sé stessi.

Quantità di numeri primi per ciascuna potenza di dieci

Fino a	Quantità di numeri primi	Proporzione di numeri primi
10	4	40%
100	25	25%
1,000	168	16.8%
10⁴	1,229	12.29%
10⁵	9,592	9.59%
10⁶	78,498	7.85%
10⁷	664,579	6.65%
10⁸	5,761,455	5.76%
10⁹	50,847,534	5.08%
10¹⁰	455,052,511	4.55%
10¹²	37,607,912,018	3.76%
10¹⁵	29,844,570,422,669	2.98%

La funzione che conta i numeri primi indica quanti ve ne siano fino a un dato valore. La proporzione diminuisce lentamente — intorno a un certo numero, all'incirca uno ogni logaritmo naturale di quel numero è primo — senza mai annullarsi: i numeri primi sono infatti infiniti.

Che cos'è uno strumento di verifica dei numeri primi

Uno strumento di verifica dei numeri primi stabilisce se un numero intero non ha altri divisori oltre a 1 e se stesso. Per i numeri piccoli è facile verificarlo a mano con le divisioni successive, ma per i numeri grandi — candidati a chiavi crittografiche, problemi di gare matematiche o numeri con centinaia di cifre — le divisioni successive diventano irrealizzabili in tempi ragionevoli, ed è necessario un test probabilistico o deterministico ibrido.

Questo strumento accetta numeri interi fino a mille cifre e sceglie automaticamente il metodo più veloce che offra comunque un risultato matematicamente affidabile: divisioni successive per i numeri piccoli, un test di Miller-Rabin deterministico per i numeri inferiori a circa 3,3 × 10²⁴, e Baillie-PSW per tutto ciò che è più grande. Mostra inoltre la scomposizione in fattori primi, i numeri primi vicini e quale test specifico ha determinato l'esito.

Come verificare se un numero è primo

Inserite il numero Digitate o incollate un numero intero fino a mille cifre nel campo di input. Virgole e spazi vengono ignorati automaticamente.
Leggete l'esito Il risultato mostra se il numero è primo, composto oppure il caso speciale dell'1, insieme al test che ha prodotto la risposta.
Controllate i dettagli Consultate la scomposizione in fattori, i numeri primi vicini e proprietà come l'appartenenza a una coppia di primi gemelli o lo stato di primo di Mersenne.
Seguite i passaggi delle divisioni Per i numeri più piccoli, una tabella mostra esattamente quali divisori sono stati provati.

Consigli per sfruttarlo al meglio

Un numero primo è un intero maggiore di uno che non ha divisori oltre a uno e a sé stesso: 2, 3, 5, 7, 11, 13 e così via, in una successione che non ha fine.
Il metodo più elementare è quello delle divisioni successive, che prova a dividere per gli interi da due fino alla radice quadrata di N. Ci si può fermare lì perché, se N è il prodotto di due fattori, il minore dei due non supera mai quella radice.
Anche a mano si escludono subito molti numeri: i pari diversi da due, quelli che terminano in cinque e quelli la cui somma delle cifre è multipla di tre sono tutti composti. Inoltre ogni primo maggiore di tre ha la forma sei k meno uno oppure sei k più uno.
Per i numeri grandi le divisioni successive non sono praticabili e si ricorre al metodo di Miller e Rabin oppure a quello di Baillie, Pomerance, Selfridge e Wagstaff. Questa pagina li realizza entrambi e restituisce l'esito in meno di un secondo anche per numeri di mille cifre.
Il numero 1 non è primo, perché la definizione richiede che sia maggiore di uno. Il 2 è invece l'unico numero primo pari: tutti i pari maggiori sono divisibili per due.

Casi d'uso

Verificare compiti o problemi di gare matematiche

Confermate rapidamente se un numero indicato come primo in una dimostrazione o in un esercizio è davvero corretto, mostrando anche la scomposizione completa se non lo è.

Esplorare i concetti di crittografia

Provate numeri candidati grandi per vedere come funziona in pratica la verifica di primalità in stile RSA, confrontando le divisioni successive con Miller-Rabin e Baillie-PSW sullo stesso input.

Controllare proprietà speciali di un numero

Scoprite se un numero è un primo gemello, un primo di Sophie Germain, di Mersenne o di Fermat senza dover consultare tabelle di riferimento.

Studiare programmazione e algoritmi

Usate la tabella dei passaggi delle divisioni successive per capire esattamente come un test di primalità arriva al suo esito, prima di implementarne uno voi stessi.

Glossario

Numero primo: Un numero intero maggiore di 1 i cui unici divisori sono 1 e se stesso. La sequenza inizia con 2, 3, 5, 7, 11, 13, … e non finisce mai.
Numero composto: Un numero intero che possiede divisori oltre a 1 e se stesso, e che può essere scritto come prodotto di numeri primi.
Divisioni successive: Verificare se un numero intero compreso tra 2 e √N divide N. È una dimostrazione completa, ma diventa troppo lenta per numeri molto grandi.
Test di Miller-Rabin: Un test basato sulle proprietà delle radici quadrate di 1 modulo N. Con basi testimoni sufficienti diventa deterministico per i numeri inferiori a circa 3,3 × 10²⁴.
Test di Baillie-PSW: Una combinazione del test di Miller-Rabin e di un forte test di Lucas, usata per i numeri troppo grandi per un test deterministico. Non è mai stato trovato un numero composto che lo superi.
Primo probabile: Un numero che ha superato un test di primalità solido come Baillie-PSW senza una dimostrazione deterministica completa: molto probabilmente primo, ma non matematicamente certo.
Numeri primi gemelli: Un numero primo che differisce da un altro numero primo esattamente di 2, come 11 e 13. Se ne esistano infinite coppie è un problema ancora aperto in matematica.
Numero primo di Mersenne: Un numero primo della forma 2^p − 1. I numeri primi più grandi mai scoperti sono quasi sempre primi di Mersenne, trovati grazie a progetti di calcolo distribuito come GIMPS.

Domande frequenti

Fino a mille cifre. Sotto dieci alla dodicesima si usano le divisioni successive, sotto 3.317.044.064.679.887.385.961.981 il metodo deterministico di Miller e Rabin e oltre quella soglia il metodo di Baillie, Pomerance, Selfridge e Wagstaff. La scomposizione e la ricerca dei primi vicini richiedono assai più calcolo e coprono quindi un intervallo più ristretto.

Gli esiti per i numeri oltre circa 3,3 per dieci alla ventiquattresima derivano dal metodo di Baillie e colleghi: non se ne conosce alcun controesempio, ma non esiste dimostrazione. Poiché è il metodo su cui si fondano anche le librerie crittografiche, l'esito è estremamente attendibile. Nel verso opposto non c'è invece alcuna ambiguità: quando compare l'esito di numero composto, è stato trovato un testimone o un divisore, e si tratta di una dimostrazione.

Perché la definizione richiede un intero maggiore di uno. Escludendolo si preserva l'unicità della scomposizione in fattori primi: se l'uno fosse primo, il sei si potrebbe scrivere come due per tre, ma anche come uno per due per tre, e il teorema fondamentale dell'aritmetica non varrebbe più.

Perché non ha divisori oltre a uno e a sé stesso e soddisfa quindi la definizione. È anche l'unico numero primo pari: ogni pari maggiore è divisibile per due e ha dunque un terzo divisore.

No. Euclide dimostrò intorno al 300 avanti Cristo che i numeri primi sono infiniti: moltiplicando fra loro un numero finito di primi e aggiungendo uno si ottiene un numero che ha un fattore primo non compreso nell'elenco. Esiste soltanto il maggiore numero primo attualmente noto, e quel primato continua a essere superato: l'ultimo è stato trovato nel 2024.

Sì: provate a dividere per i numeri primi fino alla radice quadrata. Per 391, la cui radice è circa 19,8, bastano 2, 3, 5, 7, 11, 13, 17 e 19: si scopre che è divisibile per 17 e che vale 17 per 23. Tornano utili anche i criteri come quello per cui, se la somma delle cifre è multipla di tre, il numero è divisibile per tre.

A proposito — perché i numeri primi sono importanti

I numeri primi sono spesso chiamati gli atomi dei numeri. Per il teorema fondamentale dell'aritmetica, ogni intero maggiore di uno si esprime in un solo modo come prodotto di numeri primi: essi sono dunque i mattoni indivisibili con cui si costruisce qualunque intero. È per questo che la scomposizione mostrata qui sopra è unica: 360 è due al cubo per tre al quadrato per cinque, e non c'è altro modo di scriverlo.

Stabilire se un numero enorme sia primo e scomporlo in fattori sono due problemi diversi, e la storia di quella differenza è istruttiva. Il piccolo teorema di Fermat consente verifiche rapide, ma esistono numeri composti che le superano qualunque base si scelga: il più piccolo è 561, che potete provare con i pulsanti qui sopra, ed è detto numero di Carmichael. Il metodo di Miller e Rabin chiude quella falla verificando durante il calcolo le radici quadrate di uno, ed è dimostrato che, usando come basi i primi tredici numeri primi, diventa deterministico per tutti i numeri inferiori a circa 3,3 per dieci alla ventiquattresima. Oltre quella soglia la pagina ricorre al metodo che aggiunge la prova forte di Lucas: nessun numero composto lo ha finora superato, ma poiché non ne esiste dimostrazione, per i numeri molto grandi l'esito è indicato come «probabilmente primo».

Proprio l'asimmetria fra la facilità della verifica e la difficoltà della scomposizione fonda la crittografia moderna. La crittografia RSA, che sostiene tuttora le comunicazioni sicure e le firme elettroniche, costruisce la chiave pubblica moltiplicando due grandi numeri primi: poiché ricavare da quel prodotto i fattori originari è ritenuto praticamente impossibile, la verifica resta istantanea e la scomposizione irrealizzabile. Anche questa pagina permette di sperimentare quel divario: la verifica di primalità di un numero di mille cifre si conclude quasi subito, mentre un numero composto di sessanta cifre, prodotto di due primi di trenta, resta non scomposto.

Ai numeri primi appartengono anche alcuni fra i più antichi problemi irrisolti della matematica. Nessuno sa ancora se esistano infiniti primi gemelli, come 11 e 13, benché l'infinità dei numeri primi in sé sia dimostrata da Euclide intorno al 300 avanti Cristo. Continua anche la caccia ai record: i partecipanti a un progetto di calcolo distribuito esaminano i numeri di Mersenne, della forma due elevato a p meno uno, e il maggiore numero primo oggi noto è quello trovato nel 2024, con 41.024.320 cifre.

Vedi tutte le curiosità

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	101	103	107	109	113	127	131	137	139	149	151
157	163	167	173	179	181	191	193	197	199	211	223
227	229	233	239	241	251	257	263	269	271	277	281
283	293	307	311	313	317	331	337	347	349	353	359
367	373	379	383	389	397	401	409	419	421	431	433
439	443	449	457	461	463	467	479	487	491	499	503
509	521	523	541	547	557	563	569	571	577	587	593
599	601	607	613	617	619	631	641	643	647	653	659
661	673	677	683	691	701	709	719	727	733	739	743
751	757	761	769	773	787	797	809	811	821	823	827
829	839	853	857	859	863	877	881	883	887	907	911
919	929	937	941	947	953	967	971	977	983	991	997

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	101	103	107	109	113	127	131	137	139	149	151
157	163	167	173	179	181	191	193	197	199	211	223
227	229	233	239	241	251	257	263	269	271	277	281
283	293	307	311	313	317	331	337	347	349	353	359
367	373	379	383	389	397	401	409	419	421	431	433
439	443	449	457	461	463	467	479	487	491	499	503
509	521	523	541	547	557	563	569	571	577	587	593
599	601	607	613	617	619	631	641	643	647	653	659
661	673	677	683	691	701	709	719	727	733	739	743
751	757	761	769	773	787	797	809	811	821	823	827
829	839	853	857	859	863	877	881	883	887	907	911
919	929	937	941	947	953	967	971	977	983	991	997