Provare che un milione è primo richiede mille divisioni, non un milione
Pubblicato il 16/11/2026 · 3 min di lettura · Calcolatrici quotidiane
Lena Hoffmann — Redattrice Scienza e Istruzione presso OneKitly
Matematica · Fisica
Verificato su 2 fonti
Per verificare se un numero ha un fattore, non occorre mai guardare oltre la sua radice quadrata. Se un numero si scinde in due fattori, uno sta alla radice o sotto e l'altro alla radice o sopra, quindi non trovare nulla di piccolo significa che non c'è nulla del tutto. Verificare 1 000 003 richiede dunque divisioni di prova solo fino a 1000, e le sopravvive tutte: è primo. Il suo vicino 1 000 001 cade in fretta, perché 101 lo divide esattamente lasciando 9901. La radice quadrata è ciò che trasforma una ricerca impossibile nel lavoro di un pomeriggio, ed è la prima cosa che scopre chi scrive un test di primalità.
1 000 003 è primo e la prova si ferma a 1000, la sua radice quadrata. 1 000 001 non lo è, e la ricerca finisce al terzo tentativo: 101 lo divide.
Solo i primi vanno provati
Dividere per 4 è fatica sprecata se 2 ha già fallito: l'elenco dei candidati non sono i mille numeri sotto la radice ma i 168 primi che vi si trovano. Questo solo divide il lavoro per sei, e saltare i pari e i multipli di tre cattura quasi gratis gran parte del resto. L'implementazione classica prova 2, poi 3, poi ogni numero della forma «a uno per lato di un multiplo di sei», il che copre tutti i primi possibili provando solo un terzo degli interi.
Perché il trucco smette di aiutare
Dimezzare il numero di cifre sembra molto finché il numero non è lungo. La radice quadrata di un numero di 600 cifre ne ha ancora 300, quindi la divisione di prova sulle chiavi della crittografia moderna richiederebbe più operazioni degli atomi dell'universo osservabile. I veri test di primalità abbandonano dunque la divisione e usano prove probabilistiche la cui probabilità d'errore può essere spinta sotto qualsiasi soglia. Quelle prove dimostrano che un numero è composto assai più facilmente di quanto ne esibiscano un fattore, che è esattamente l'asimmetria su cui poggia la sicurezza.
| Numero | Divisioni da provare | Risultato |
|---|---|---|
| 1 000 001 | 3 prima di fallire | 101 × 9901 |
| 1 000 003 | 168 primi fino a 1000 | Primo |
| Un numero di 600 cifre | Più degli atomi nell'universo | Inutilizzabile |
Domande frequenti
- Perché 1 non è primo?
- Per decisione, per mantenere unica la fattorizzazione. Se 1 contasse, 12 potrebbe scriversi 2×2×3, o 1×2×2×3, o 1×1×2×2×3, e l'enunciato che ogni numero ha esattamente una fattorizzazione in primi avrebbe bisogno di una clausola d'eccezione. Le tavole dell'Ottocento elencavano davvero 1 fra i primi, e la convenzione cambiò perché ogni teorema risultava più pulito senza. Le definizioni in matematica si scelgono per le loro conseguenze più di quanto si scoprano, e questo è il più chiaro dei piccoli esempi.
- Come verifico un numero a mano?
- Prendete la radice quadrata, arrotondate per eccesso e dividete per ogni primo fino a lì. Sotto diecimila sono al massimo 25 divisioni, la maggior parte delle quali si liquidano all'istante: i pari falliscono su 2, le somme di cifre divisibili per tre falliscono su 3, tutto ciò che finisce in 0 o 5 fallisce su 5. Ciò che sopravvive per essere provato sul serio è un elenco corto. Sopra il milione il metodo diventa noioso più che difficile, ed è esattamente il momento di affidarlo a una macchina.
Articoli che potrebbero interessarti
Tutte le guide →Strumenti correlati
Fonti
Hai notato un errore in questo articolo?