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.
Consigli
- 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.
Domande frequenti
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.