Interpretare i risultati
La tabella seguente riporta i tre risultati per alcuni valori di esempio.
| Numero inserito | Primo? | Scomposizione | Primo successivo |
|---|---|---|---|
| 97 | Sì | 97 | 101 |
| 84 | No | 2 x 2 x 3 x 7 | 89 |
| 100 | No | 2 x 2 x 5 x 5 | 101 |
| 2 | Sì (unico primo pari) | 2 | 3 |
| 1 | No (né primo né composto) | - | 2 |
- Il numero 1 non è primo: i primi devono avere esattamente due divisori distinti, mentre 1 ne ha uno solo. Escludere 1 preserva l'unicità della scomposizione in fattori primi.
- Le divisioni di prova sono esatte ma rallentano molto con numeri grandi; questo calcolatore accetta valori fino a 10^12, dove la ricerca prova i divisori fino a un milione.
- Nella gamma considerata la ricerca del primo successivo termina rapidamente in modo garantito: per il postulato di Bertrand esiste sempre un numero primo compreso fra n e 2n.
Che cos'è un numero primo?
Un numero primo è un numero naturale maggiore di 1 che possiede esattamente due divisori positivi: 1 e se stesso. I primi numeri primi sono 2, 3, 5, 7, 11, 13, 17, 19, 23 e 29. Il 2 è l'unico primo pari, poiché ogni altro numero pari è divisibile per 2. I numeri maggiori di 1 che non sono primi si dicono composti, mentre 1 non è né primo né composto, per definizione.
Il teorema fondamentale dell'aritmetica afferma che ogni intero maggiore di 1 può essere scritto come prodotto di numeri primi in un solo modo, a meno dell'ordine dei fattori. È questa unicità della scomposizione a fare dei primi i mattoni costitutivi degli interi: 84 = 2^2 x 3 x 7 e nessun'altra combinazione di primi dà 84 come prodotto.
I numeri primi sono infiniti — risultato dimostrato da Euclide attorno al 300 a.C. — e si diradano al crescere dei numeri, pur senza seguire alcuno schema semplice. I primi di grandi dimensioni sono alla base della moderna crittografia a chiave pubblica (come RSA), che si fonda sulla difficoltà pratica di fattorizzare il prodotto di due primi molto grandi.
Come usare questo calcolatore di numeri primi
- Inserisci un numero intero n pari almeno a 1. I decimali vengono arrotondati per difetto all'intero più vicino.
- Leggi il verdetto sulla primalità: un segno di spunta indica che il numero è primo, una croce che è composto (oppure 1, che non è né l'uno né l'altro).
- Leggi la scomposizione in fattori primi, ossia l'unico prodotto di primi uguale al tuo numero. Per un numero primo la scomposizione coincide con il numero stesso.
- Leggi il primo successivo, cioè il più piccolo numero primo strettamente maggiore del tuo.
Come si verifica la primalità: le divisioni di prova
Un numero n è composto se e solo se ammette un divisore maggiore di 1 e non superiore alla radice quadrata di n. I divisori infatti si presentano a coppie: se n = a x b con a <= b, allora a <= sqrt(n). Le divisioni di prova devono dunque testare i possibili divisori solo fino a √n e, una volta controllato il 2, bastano i candidati dispari.
Esempio svolto (numero primo): n = 97. La radice quadrata di 97 vale circa 9,85, perciò è sufficiente provare 2, 3, 5, 7 e 9. Il 97 è dispari; 9 + 7 = 16 non è divisibile per 3; non termina né per 0 né per 5; 97 / 7 = 13,857...; e 97 / 9 non dà un intero. Non esiste alcun divisore, dunque 97 è primo.
Esempio svolto (scomposizione): n = 84. Si dividono via i primi partendo dal più piccolo: 84 / 2 = 42, 42 / 2 = 21, 21 / 3 = 7, e 7 è primo. Perciò 84 = 2 x 2 x 3 x 7 = 2^2 x 3 x 7. Il primo successivo a 84 è 89 (85 = 5 x 17, 86 = 2 x 43, 87 = 3 x 29, 88 = 2^3 x 11).
Errori comuni
- Considerare 1 come numero primo: per definizione un primo ha esattamente due divisori distinti, mentre 1 ne ha uno solo.
- Ritenere che tutti i primi siano dispari: il 2 è primo ed è l'unico primo pari.
- Provare i divisori fino a n anziché fermarsi a √n: qualunque numero composto ha un fattore pari o inferiore alla propria radice quadrata.
- Credere che tutti i numeri dispari siano primi: 9 = 3 x 3, 15 = 3 x 5 e 21 = 3 x 7 sono dispari e composti.
- Confondere la scomposizione in fattori primi con una scomposizione qualsiasi: 84 = 4 x 21 è una scomposizione, ma quella in fattori primi è 2 x 2 x 3 x 7.
Domande frequenti
Come si verifica se un numero è primo?
Si controlla se un qualsiasi intero da 2 fino alla radice quadrata del numero lo divide esattamente. Se nessuno lo fa, il numero è primo. Per 97 la radice quadrata vale circa 9,85 e nessuno fra 2, 3, 5, 7 e 9 divide 97, dunque 97 è primo. Le coppie di divisori garantiscono che ogni numero composto abbia un fattore pari o inferiore alla propria radice quadrata.
Perché 1 non è un numero primo?
Un primo è definito come dotato di esattamente due divisori positivi distinti, 1 e se stesso, mentre il numero 1 ne ha uno soltanto. La definizione tutela inoltre il teorema fondamentale dell'aritmetica: se 1 fosse primo, le scomposizioni non sarebbero più uniche (6 = 2 x 3 = 1 x 2 x 3 = 1 x 1 x 2 x 3, e così via).
Che cos'è la scomposizione in fattori primi?
È l'espressione di un numero come prodotto di numeri primi, che il teorema fondamentale dell'aritmetica garantisce unica a meno dell'ordine. Per esempio, 84 = 2 x 2 x 3 x 7. Per ottenerla si divide ripetutamente per il più piccolo primo che dà resto zero, finché il quoziente residuo è 1 oppure è a sua volta primo.
Il 2 è un numero primo?
Sì: 2 è primo perché i suoi unici divisori sono 1 e 2, ed è l'unico primo pari. Ogni altro numero pari è divisibile per 2 e dunque composto. È per questo che i test di primalità trattano il 2 a parte e poi verificano soltanto i candidati dispari.
Quanti sono i numeri primi?
Sono infiniti, come dimostrò Euclide attorno al 300 a.C.: dato un qualunque elenco finito di primi, il numero ottenuto moltiplicandoli tutti e aggiungendo 1 non è divisibile per nessuno di essi, dunque nell'elenco manca almeno un primo. I primi si diradano al crescere dei numeri — per il teorema dei numeri primi la loro densità vicino a n è all'incirca 1 / ln(n) — ma non si esauriscono mai.
Perché i numeri primi contano in crittografia?
I sistemi a chiave pubblica come RSA poggiano su un'asimmetria: moltiplicare due primi grandi è facile, mentre risalire ai primi dal loro prodotto è computazionalmente arduo alle dimensioni usate nella pratica (centinaia di cifre). Le chiavi di sicurezza si costruiscono a partire da tali prodotti, perciò la generazione di primi e i test di primalità sono operazioni crittografiche fondamentali.
Fonti
- Weisstein, Eric W. "Prime Number" and "Fundamental Theorem of Arithmetic." MathWorld — A Wolfram Web Resource. mathworld.wolfram.com.
- Hardy GH, Wright EM. An Introduction to the Theory of Numbers. Oxford University Press (primes, unique factorization, Bertrand's postulate).
- Euclid. Elements, Book IX, Proposition 20 (infinitude of primes).