Test di Primalità

Un Test di Primalità è un procedimento o algoritmo che consente di determinare se un numero intero passato come input è un numero primo o no.

Esistono diversi metodi per verificare se un numero è primo. In questa lezione, vedremo come funziona il test di primalità per divisioni ripetute e alcune ottimizzazioni per velocizzarlo.

Test di Primalità

Come si evince dalla definizione, un numero primo è divisibile solo per 1 e per se stesso. Ciò significa che esso non sarà divisibile per tutti gli altri numeri compresi tra 1 e se stesso.

Verificare se un numero naturale è primo è un problema molto importante in matematica e in informatica. Questo problema è noto come Test di Primalità.

Esistono diversi metodi per verificare se un numero è primo oppure no. Alcuni di essi sfruttano le proprietà dei numeri primi, altri sono basati su algoritmi più complessi. Questo è un argomento molto vasto e complesso che viene affrontato in Teoria dei Numeri.

In questa lezione, ci concentreremo sul metodo più semplice per verificare se un numero è primo: il test di primalità per divisioni ripetute.

In pratica, dato un numero $n$ , per verificare se esso è primo, si procede a dividere $n$ per tutti i numeri compresi tra 2 e $n - 1$ . Se nessuno di questi numeri è divisore di $n$ , allora $n$ è un numero primo.

Prendiamo un primo esempio. Verifichiamo se il numero $23$ è primo.

Per farlo, dobbiamo dividere $23$ per tutti i numeri naturali compresi tra $2$ e $22$ . In questo caso, dobbiamo dividere $23$ per $2$ , $3$ , $4$ e così via:

$23$ non è divisibile per $2$ ;
$23$ non è divisibile per $3$ ;
$23$ non è divisibile per $4$ ;
$23$ non è divisibile per $5$ ;
$23$ non è divisibile per $6$ ;
...
$23$ non è divisibile per $22$ ;

Poiché nessuno di questi numeri è divisore di $23$ , possiamo concludere che $23$ è un numero primo.

Prendiamo un secondo esempio. Verifichiamo se il numero $77$ è primo.

Per farlo, dobbiamo dividere $77$ per tutti i numeri naturali compresi tra $2$ e $77 - 1 = 76$ . In questo caso, dobbiamo dividere $77$ per $2$ , $3$ , $4$ , $5$ , $6$ , $7$ , $8$ e così via:

$77$ non è divisibile per $2$ ;
$77$ non è divisibile per $3$ ;
$77$ non è divisibile per $4$ ;
$77$ non è divisibile per $5$ ;
$77$ non è divisibile per $6$ ;
$77$ è divisibile per $7$ ;

Poiché $77$ è divisibile per $7$ , possiamo concludere che $77$ non è un numero primo e ci possiamo fermare.

Così come descritto il test è abbastanza tedioso ma si possono applicare alcune ottimizzazioni.

Ottimizzazioni

In primo luogo, possiamo arrestare il procedimento di verifica al numero $\sqrt{n}$ .

Il motivo per cui si considerano solo i numeri fino a $\sqrt{n}$ è che, se un numero $n$ è divisibile per un numero $a$ maggiore di $\sqrt{n}$ , allora deve essere divisibile anche per un numero $b$ minore di $\sqrt{n}$ .

Una seconda ottimizzazione con cui possiamo velocizzare il procedimento di verifica di primalità è quella di dividere il numero solo per i numeri primi compresi tra $2$ e $\sqrt{n}$ .

La ragione è molto semplice. Intuitivamente, ritornando all'esempio di $77$ , poiché esso non è divisibile ne per $2$ ne per $3$ , che sono primi, allora non sarà divisibile ne per $6$ , che è pari a $2 \cdot 3$ , ne per $9$ , ossia $3 \cdot 3$ , e così via. In altre parole, se un numero non è divisibile per un numero primo, allora non sarà divisibile per i multipli di quel numero primo.

Applicando queste due ottimizzazioni, il procedimento diventa molto più veloce. Ad esempio, supponiamo di voler verificare se $123$ sia primo oppure no.

In questo caso, dobbiamo dividere $123$ solo per i numeri primi compresi tra $2$ e $\sqrt{123} \approx 11$ . Quindi, dobbiamo dividere $123$ per $2$ , $3$ , $5$ , $7$ e $11$ :

$123$ non è divisibile per $2$ ;
$123$ non è divisibile per $3$ ;
$123$ non è divisibile per $5$ ;
$123$ non è divisibile per $7$ ;
$123$ non è divisibile per $11$ ;

Poiché nessuno di questi numeri è divisore di $123$ , possiamo concludere che $123$ è un numero primo. Abbiamo effettuato soltanto $5$ divisioni anziché $121$ divisioni.

Ricapitolando:

Definizione

Test di Primalità per divisioni ripetute

Per verificare se un numero naturale $n$ è primo, si procede a dividere $n$ per tutti i numeri primi compresi tra $2$ e $\sqrt{n}$ . Se nessuno di questi numeri è divisore di $n$ , allora $n$ è un numero primo.

Esistono altri test di primalità più rapidi e complessi di quello appena descritto. Tuttavia, essi si basano su concetti e tecniche più avanzate che esulano dagli argomenti trattati in questa lezione e richiedono una conoscenza più approfondita della Teoria dei Numeri.

Implementazione in Pseudo-Codice

Possiamo provare ad implementare in pseudo-codice il test di primalità per divisioni ripetute:

**Figura 1:** Test di Primalità per divisioni ripetute in pseudo-codice

Nel codice sopra, la funzione ${{\rm C{\small RIVELLO}\;D{\small I}\;E{\small RATOSTENE}}}(n)$ restituisce una lista di numeri primi fino a $\sqrt{n}$ . Abbiamo visto come realizzarla nella lezione sul crivello di eratostene.

Invece, la funzione ${{\rm R{\small ESTO}(n, p)}}$ restituisce il resto della divisione tra $n$ e $p$ . Se il resto è uguale a $0$ , allora $n$ è divisibile per $p$ . In molti linguaggi di programmazione questa funzione viene chiamata MOD che sta per modulo.

In Sintesi

Riassumendo questa lezione, i punti principali sono:

Un test di primalità consente di determinare se un numero naturale è primo o no. Ne esistono diversi tipi, alcuni più semplici e altri più complessi.
Il metodo più semplice per verificare se un numero è primo è il test di primalità per divisioni ripetute.
Per verificare se un numero $n$ è primo, si procede a dividere $n$ per tutti i numeri primi compresi tra $2$ e $\sqrt{n}$ . Se nessuno di questi numeri è divisore di $n$ , allora $n$ è un numero primo.

Lezione Precedente Indice del capitolo