Verifica Numero Primo

Che cos'è un numero primo

Un numero primo è un numero naturale maggiore di 1 che si può dividere in modo esatto — cioè senza resto — soltanto per 1 e per sé stesso. Detto in altri termini, un numero primo ha esattamente due divisori distinti. Il 7, per esempio, è primo perché i suoi unici divisori sono 1 e 7; il 12, invece, non lo è, perché oltre a 1 e 12 è divisibile anche per 2, 3, 4 e 6.

I numeri maggiori di 1 che non sono primi si chiamano numeri composti: hanno cioè almeno un divisore diverso da 1 e da sé stessi. Ogni numero composto può essere "spezzato" in un prodotto di fattori più piccoli. I primi numeri primi, in ordine crescente, sono 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 e così via: sono infiniti, come dimostrò Euclide più di duemila anni fa.

Un caso che merita attenzione è il 2: è l'unico numero primo pari. Tutti gli altri numeri pari sono divisibili per 2 e quindi composti, mentre il 2 sfugge alla regola perché i suoi soli divisori restano 1 e 2. Da qui in poi, tutti i numeri primi sono dispari — ma attenzione, non tutti i dispari sono primi (il 9, per esempio, è dispari ma divisibile per 3).

Il calcolatore di questa pagina risponde alla domanda più comune: un dato numero è primo oppure no? Inserendo un valore, ottieni la risposta, la lista completa dei suoi divisori e il loro numero. Con il valore predefinito 7 il risultato è "è un numero primo", con divisori 1 e 7 e un totale di 2 divisori.

Perché 1 non è un numero primo

È l'aspetto che genera più confusione, e vale la pena chiarirlo subito: il numero 1 non è primo. La definizione richiede esattamente due divisori distinti, mentre l'1 ne ha uno solo (sé stesso). Non è però nemmeno composto: appartiene a una categoria a parte, quella delle "unità". Il calcolatore, coerentemente, per l'1 restituisce "non è un numero primo".

La scelta di escludere l'1 non è un capriccio, ma serve a mantenere valido uno dei risultati più importanti della matematica: il teorema fondamentale dell'aritmetica. Questo teorema afferma che ogni numero naturale maggiore di 1 si può scrivere in un unico modo come prodotto di numeri primi (a meno dell'ordine dei fattori). Se l'1 fosse primo, questa unicità cadrebbe: si potrebbe moltiplicare per 1 quante volte si vuole (12 = 2 × 2 × 3 = 1 × 2 × 2 × 3 = …) e la scomposizione non sarebbe più unica.

Anche lo 0 e i numeri negativi restano fuori dal discorso: la nozione di numero primo si applica per definizione ai soli numeri naturali maggiori di 1. Il calcolatore infatti considera il valore assoluto e la sua parte intera, quindi per numeri minori di 2 risponde sempre che non sono primi.

Ricordare questa eccezione evita l'errore più tipico dei problemi scolastici, dove capita di includere l'1 tra i primi. La regola pratica da tenere a mente è semplice: si parte a contare i numeri primi dal 2, mai dall'1.

Come si verifica se un numero è primo

Il metodo diretto per stabilire se un numero n è primo consiste nel provare a dividerlo per tutti i numeri interi da 2 in su: se ne trovi anche uno solo che lo divide senza resto, il numero è composto; se non ne trovi nessuno, è primo. Questo procedimento si chiama "divisione per tentativi".

C'è però una scorciatoia fondamentale che rende il controllo molto più veloce: non serve arrivare fino a n, ma basta fermarsi alla radice quadrata di n. Il motivo è geometrico prima ancora che aritmetico. Se n avesse un divisore più grande della sua radice quadrata, il divisore "complementare" (cioè n diviso quel numero) sarebbe più piccolo della radice — e quindi lo avresti già incontrato controllando i numeri piccoli. In pratica i divisori si presentano sempre in coppia, uno sotto e uno sopra la radice quadrata.

Prendiamo il 97. La sua radice quadrata è circa 9,85, quindi basta provare a dividerlo per i numeri da 2 a 9. Nessuno di questi lo divide esattamente: il 97 è primo. Provare i numeri da 10 in su sarebbe stato inutile. Se invece prendiamo il 91, tra i numeri fino a √91 ≈ 9,54 troviamo il 7 (91 = 7 × 13): il 91 è quindi composto, anche se a prima vista può sembrare primo.

È esattamente questo l'algoritmo che usa il calcolatore: controlla i possibili divisori solo fino alla radice quadrata del numero, il che gli permette di rispondere in un istante anche su valori grandi. La radice quadrata è quindi uno strumento chiave qui, ed è la stessa idea che ritrovi nella pagina dedicata al calcolo della radice quadrata.

• Passo 1 — Se il numero è minore di 2, non è primo (l'1, lo 0 e i negativi sono esclusi).
• Passo 2 — Prova a dividerlo per ogni intero da 2 fino alla sua radice quadrata.
• Passo 3 — Se uno lo divide senza resto, è composto; se nessuno lo divide, è primo.

Esempio: verificare 7 e 8 passo per passo

Partiamo dal valore predefinito del calcolatore, il 7. La sua radice quadrata è circa 2,65, quindi l'unico numero da testare è il 2. Il 7 diviso 2 dà 3 con resto 1: non è una divisione esatta. Non ci sono altri divisori da provare, quindi il 7 è primo. I suoi divisori completi sono 1 e 7, per un totale di 2 — esattamente ciò che restituisce il calcolatore.

Confrontiamolo con l'8. La sua radice quadrata è circa 2,83, quindi anche qui basta testare il 2. Ma 8 diviso 2 fa 4, senza resto: abbiamo trovato un divisore. L'8 è dunque composto. I suoi divisori completi sono 1, 2, 4 e 8, quindi quattro divisori in tutto. Basta un solo divisore "in mezzo" per far scattare la classificazione da primo a composto.

Un ultimo esempio istruttivo è il 51, che molti scambiano per primo. La sua radice quadrata è circa 7,14, perciò si testano 2, 3, 5, 7. Il 3 lo divide: 51 = 3 × 17. Il 51 è composto, e i suoi divisori sono 1, 3, 17, 51. Questo mostra perché non bisogna fidarsi dell'intuizione: numeri dall'aria "strana" possono nascondere fattori piccoli.

La tabella seguente riassume alcuni casi tipici, mettendo a confronto numeri primi e composti con i rispettivi divisori.

A cosa servono i numeri primi

I numeri primi non sono una curiosità astratta: sono i "mattoni" con cui si costruiscono tutti gli altri numeri. Grazie al teorema fondamentale dell'aritmetica, ogni numero intero maggiore di 1 si scompone in un prodotto di primi in un unico modo. Questa scomposizione, detta fattorizzazione, è alla base di operazioni quotidiane in matematica: per esempio serve a calcolare il massimo comune divisore e il minimo comune multiplo, e quindi a semplificare o sommare frazioni.

Proprio per questo, sapere riconoscere i numeri primi è utile quando lavori con le frazioni: ridurre una frazione ai minimi termini significa eliminare i fattori comuni a numeratore e denominatore, e i primi sono i fattori "ultimi" che non si possono più spezzare. Le pagine dedicate al calcolo delle frazioni, al calcolo del MCD e al calcolo del mcm sfruttano tutte questa idea.

L'applicazione più celebre dei numeri primi, però, è nella crittografia moderna. La sicurezza di molte comunicazioni digitali — dagli acquisti online alle app di messaggistica — si basa sul fatto che moltiplicare due numeri primi enormi è facilissimo, ma fare il percorso inverso (ritrovare i due primi a partire dal prodotto) è, con i numeri giusti, praticamente impossibile in tempi ragionevoli. È questa "asimmetria" a proteggere i tuoi dati.

I numeri primi compaiono infine in molti altri contesti: nella generazione di numeri casuali, negli algoritmi informatici, nel funzionamento di alcuni ingranaggi (usare un numero primo di denti riduce l'usura), e persino in natura, come nei cicli vitali di certe cicale che emergono ogni 13 o 17 anni, due numeri primi che riducono gli incontri con i predatori.

Errori comuni da evitare

Il primo errore, il più diffuso, è considerare l'1 un numero primo. Come abbiamo visto, l'1 ha un solo divisore e per convenzione matematica non è primo. Chi lo include sbaglia il conteggio dei primi e rischia di invalidare regole importanti come la fattorizzazione unica.

Il secondo errore è pensare che tutti i numeri dispari siano primi. È vero il contrario del sospetto comune: molti dispari sono composti. Il 9 (3 × 3), il 15 (3 × 5), il 21 (3 × 7), il 25 (5 × 5) e il 27 (3 × 9) sono tutti dispari ma non primi. L'unica cosa certa è che, a parte il 2, un numero primo deve essere dispari — non che ogni dispari sia primo.

Un terzo errore è dimenticare che il 2 è primo perché si dà per scontato che "i pari non lo siano mai". Il 2 è l'eccezione: è pari e primo allo stesso tempo, essendo divisibile solo per 1 e per 2. Escluderlo dall'elenco dei primi è un abbaglio frequente.

Infine, un errore pratico è provare a dividere il numero per troppi valori, arrivando fino a n invece di fermarsi alla sua radice quadrata. Non è sbagliato, ma è enormemente più lento e inutile: superata la radice quadrata, ogni eventuale divisore sarebbe già stato scoperto tra i numeri piccoli. Il controllo intelligente si ferma a √n.