Algoritmi numerici¶

Parte 1 · Algoritmi di base · Capitolo 5 · Dispensa, volume 1 (PDF) · Esercizi: Algoritmi numerici · App: Euclide e crivello di Eratostene

Introduzione¶

In questo capitolo studiamo quattro algoritmi classici che operano sui numeri naturali:

il cambio di base, che scrive un numero naturale dato in base dieci come sequenza di cifre in un'altra base $b$;
il test di primalità, che decide se un numero naturale è primo;
il crivello di Eratostene, che trova tutti i numeri primi fino a un dato numero naturale;
l'algoritmo di Euclide, che calcola il massimo comun divisore di due numeri naturali.

Tutti e quattro gli algoritmi si basano su una sola operazione elementare, la divisione con resto: il cambio di base legge le cifre come resti, il test di primalità e il crivello cercano resti uguali a zero, e l'algoritmo di Euclide sostituisce una coppia di numeri con una coppia più piccola per mezzo di un resto. Per ogni algoritmo presentiamo lo pseudocodice (con array indicizzati a partire da $1$) e un'esecuzione passo per passo; le implementazioni in Python, C++ e Java (con array indicizzati a partire da $0$), eseguite sugli stessi input, sono nei notebook Colab del capitolo.

5.1 Cambio di base¶

Nel capitolo «Rappresentazione dei numeri» abbiamo visto che una sequenza di $k$ cifre $(d_{k-1} \dots d_1 d_0)_b$ in base $b$ rappresenta il numero naturale $\sum_{i=0}^{k-1} d_i \, b^i$, e che servono $\lfloor \log_b n \rfloor + 1$ cifre per scrivere un numero naturale $n \ge 1$ in base $b$. In questa sezione risolviamo il problema inverso: dato $n$ in base dieci, calcoliamo le sue cifre in base $b$.

5.1.1 Divisione con resto¶

Definizione 5.1: divisione con resto

Dati un numero naturale $n$ e un numero naturale $b \ge 1$, la divisione con resto (o divisione euclidea) di $n$ per $b$ determina i due numeri naturali $q$ e $r$ tali che

\[ n = q \; b + r \qquad \text{con} \qquad 0 \le r < b . \]

Il numero $n$ si chiama dividendo, $b$ divisore, $q$ quoziente e $r$ resto. I due numeri $q$ e $r$ sono unici, e scriviamo

\[ q = \lfloor n / b \rfloor \qquad \text{e} \qquad r = n \bmod b . \]

Il fatto chiave alla base del cambio di base è che una divisione per $b$ estrae la cifra meno significativa di $n$ in base $b$ e lascia come quoziente il numero formato dalle cifre rimanenti.

Osservazione 5.2

Sia $n \ge 1$ un numero naturale la cui rappresentazione in base $b \ge 2$ è $(d_{k-1} \dots d_1 d_0)_b$. Allora

\[ n \bmod b = d_0 \qquad \text{e} \qquad \lfloor n / b \rfloor = \sum_{i=1}^{k-1} d_i \, b^{i-1} = (d_{k-1} \dots d_1)_b , \]

dove il quoziente è $0$ se $k = 1$.

Dimostrazione

Raccogliendo il fattore $b$ da tutti i termini con $i \ge 1$, otteniamo

\[ n = \sum_{i=0}^{k-1} d_i \, b^i = \Big( \sum_{i=1}^{k-1} d_i \, b^{i-1} \Big) \, b + d_0 . \]

Poiché $d_0$ è una cifra in base $b$, si ha $0 \le d_0 < b$. Per l'unicità del quoziente e del resto della divisione con resto, il quoziente di $n$ diviso $b$ è $\sum_{i=1}^{k-1} d_i \, b^{i-1}$ e il resto è $d_0$. □

Dividendo $n$ per $b$, il resto è la cifra meno significativa $d_0$, e il quoziente è il numero scritto con le altre cifre $(d_{k-1} \dots d_1)_b$. Dividendo di nuovo il quoziente per $b$ si ottiene $d_1$, e così via: ripetendo la divisione fino a ottenere quoziente $0$ si producono tutte le cifre di $n$ in base $b$, dalla meno significativa alla più significativa, in esattamente $\lfloor \log_b n \rfloor + 1$ divisioni.

5.1.2 L'algoritmo¶

Dato un numero naturale $n>0$ rappresentato in base 10 (decimale) e una base di arrivo $b \geq 2$, consideriamo il problema di convertire $n$ in base $b$.

Pseudocodice dell'algoritmo per convertire sequenze di cifre dalla base dieci alla base $b$:

Algoritmo: ChangeOfBase

Input: Un numero naturale $n \ge 1$ (in base 10) e una base $b \ge 2$

Output: Un array $d[1..nd]$ di cifre in base $b$ e il numero di cifre $nd$

1function ChangeOfBase(n, b)

2$nd$ := $\lfloor \log_b n \rfloor + 1$// Numero di cifre necessarie

3$d$ := new array$[1..nd]$

4$k$ := $1$

5while $n > 0$ do

6$q$ := $\lfloor n / b \rfloor$// Quoziente

7$r$ := $n \bmod b$// Resto (cifra in base $b$)

8$d[k]$ $\leftarrow$ $r$

9$n$ $\leftarrow$ $q$

10$k$ $\leftarrow$ $k + 1$

11end

12return $d, nd$

13end

Esegui in Colab:Python C++Java

Spiegazione:
- L'algoritmo calcola il numero di cifre $nd$ necessarie per rappresentare $n$ in base $b$ con la formula $\lfloor \log_b n \rfloor + 1$.
- Inizializza un array $d[1..nd]$ per memorizzare le cifre e un contatore $k$ che tiene traccia della posizione corrente.
- Il ciclo principale divide ripetutamente $n$ per $b$ per estrarre le cifre da destra a sinistra (dalla meno significativa alla più significativa).
- A ogni iterazione il resto $r = n \bmod b$ fornisce la cifra successiva, che viene memorizzata in $d[k]$.
- Il quoziente $q = \lfloor n / b \rfloor$ diventa il nuovo valore di $n$ per l'iterazione successiva.
- L'algoritmo termina quando $n = 0$, restituendo l'array $d$ e il numero totale di cifre $nd$.
- Le cifre in $d$ sono memorizzate in ordine inverso: l'elemento $d[k]$ è la cifra $d_{k-1}$ di peso $b^{k-1}$, quindi $d[1] = d_0$ è la cifra meno significativa (la più a destra) e $d[nd] = d_{nd-1}$ è la cifra più significativa (la più a sinistra).

Esempio 5.1: conversione dalla base dieci alla base $b$

Conversione di $7$ in base $b=2$:

iterazione $k$	$n$	$n/b$	$q$	$r$	cifra
$1$	$7$	$7/2$	$3$	$1$	$d[1] = d_{0}$ (meno significativa)
$2$	$3$	$3/2$	$1$	$1$	$d[2] = d_{1}$
$3$	$1$	$1/2$	$0$	$1$	$d[3] = d_{2}$ (più significativa)

Quindi $7$ in base $2$ è $(111)_{2}$, con $nd = \lfloor \log_{2} 7 \rfloor + 1 = 3$ cifre.

Conversione di $8$ in base $b=2$:

iterazione $k$	$n$	$n/b$	$q$	$r$	cifra
$1$	$8$	$8/2$	$4$	$0$	$d[1] = d_{0}$ (meno significativa)
$2$	$4$	$4/2$	$2$	$0$	$d[2] = d_{1}$
$3$	$2$	$2/2$	$1$	$0$	$d[3] = d_{2}$
$4$	$1$	$1/2$	$0$	$1$	$d[4] = d_{3}$ (più significativa)

Quindi $8$ in base $2$ è $(1000)_{2}$, con $nd = \lfloor \log_{2} 8 \rfloor + 1 = 4$ cifre.

Conversione di $25$ in base $b=3$:

iterazione $k$	$n$	$n/b$	$q$	$r$	cifra
$1$	$25$	$25/3$	$8$	$1$	$d[1] = d_{0}$ (meno significativa)
$2$	$8$	$8/3$	$2$	$2$	$d[2] = d_{1}$
$3$	$2$	$2/3$	$0$	$2$	$d[3] = d_{2}$ (più significativa)

Quindi $25$ in base $3$ è $(221)_{3}$, con $nd = \lfloor \log_{3} 25 \rfloor + 1 = 3$ cifre.

Conversione di $100$ in base $b=8$:

iterazione $k$	$n$	$n/b$	$q$	$r$	cifra
$1$	$100$	$100/8$	$12$	$4$	$d[1] = d_{0}$ (meno significativa)
$2$	$12$	$12/8$	$1$	$4$	$d[2] = d_{1}$
$3$	$1$	$1/8$	$0$	$1$	$d[3] = d_{2}$ (più significativa)

Quindi $100$ in base $8$ è $(144)_{8}$, con $nd = \lfloor \log_{8} 100 \rfloor + 1 = 3$ cifre.

Punti chiave.

Il resto della divisione di $n$ per $b$ è la cifra meno significativa di $n$ in base $b$; il quoziente è il numero scritto con le altre cifre.
L'algoritmo esegue una divisione per ogni cifra: $\lfloor \log_b n \rfloor + 1$ iterazioni.
Le cifre vengono prodotte dalla meno significativa alla più significativa, quindi il risultato si legge al contrario: da $d[nd]$ a $d[1]$.

5.2 Test di primalità¶

Il cambio di base usa il resto $n \bmod b$ per leggere una cifra. Un resto uguale a zero ha un significato proprio: dice che la divisione è esatta, cioè che $b$ è un divisore di $n$. Contare i divisori porta ai numeri primi.

Definizione 5.3: divisore

Un numero naturale $d \ge 1$ è un divisore di un numero naturale $n$ se esiste un numero naturale $k$ tale che $n = k \; d$:

\[ \text{$d$ è un divisore di $n$} \quad \Longleftrightarrow \quad \exists\, k \in \N,\ n = k \; d \]

o, equivalentemente, se $n \bmod d = 0$.

Definizione 5.4: numero primo

Un numero naturale $n \ge 2$ è primo se i suoi unici divisori sono $1$ e $n$ stesso. Un numero naturale $n \ge 2$ che non è primo si dice composto: ha un divisore $d$ con $2 \le d \le n-1$. I numeri $0$ e $1$ non sono primi.

Dato un numero naturale $n$, consideriamo il problema di stabilire se $n$ è un numero primo.

5.2.1 Un primo algoritmo¶

La definizione suggerisce un algoritmo diretto: provare, uno per uno, i candidati divisori di $n$ diversi da $1$ e da $n$. L'osservazione seguente mostra che i candidati maggiori di $n/2$ si possono saltare.

Osservazione 5.5

Per ogni numero naturale $n \ge 2$, se $d$ è un divisore di $n$ con $d < n$, allora $d \le n/2$.

Dimostrazione

Poiché $d$ è un divisore di $n$, esiste un numero naturale $k$ tale che $n = k \; d$. Poiché $d < n$, si ha $k \ge 2$, quindi

\[ d = \frac{n}{k} \le \frac{n}{2} . \]

□

Ne segue che basta controllare se qualche numero naturale $d$ in $\{2, 3, \dots, \lfloor n/2 \rfloor\}$ è un divisore di $n$. Se non esiste alcun divisore di questo tipo, $n$ è primo.
Pseudocodice dell'algoritmo Basic Primality Test (test di primalità di base):

Algoritmo: BasicPrimalityTest

Input: Un numero naturale $n$

Output: true se $n$ è primo, false altrimenti

1function BasicPrimalityTest(n)

2if $n < 2$ then

3return false// 0 e 1 non sono primi

4end

5for $d := 2$ to $\lfloor n/2 \rfloor$ do

6if $n \bmod d = 0$ then

7return false// $d$ divide $n$: non primo

8end

9end

10return true// Nessun divisore trovato: $n$ è primo

11end

Esegui in Colab:Python C++Java

Spiegazione dell'algoritmo:
- I numeri minori di $2$ non sono primi per definizione.
- Il ciclo prova ogni candidato divisore $d$ da $2$ fino a $\lfloor n/2 \rfloor$.
- Se $d$ è un divisore di $n$ (cioè $n \bmod d = 0$), la funzione restituisce subito false.
- Se il ciclo termina senza trovare alcun divisore, $n$ è primo e la funzione restituisce true.
Per un numero primo il ciclo viene eseguito per intero: per $n = 29$ l'algoritmo prova i $13$ candidati $d = 2, 3, \dots, 14$. Mostriamo ora che bastano molti meno candidati.

5.2.2 Provare i divisori fino a $\sqrt{n}$¶

I divisori di un numero naturale si presentano a coppie: $d$ e $n/d$. In ogni coppia, uno dei due numeri è al più $\sqrt{n}$.

Osservazione 5.6

Per ogni numero naturale $n \ge 2$, se $d$ è un divisore di $n$ allora $n/d$ è un divisore di $n$.

Dimostrazione

Se $d$ è un divisore di $n$, allora esiste un numero naturale $k$ tale che

\[ n = k \; d. \]

Poiché $k = n/d$, ne segue che $n/d$ è un numero naturale. Quindi

\[ n = d \left(\frac{n}{d}\right), \]

quindi anche $n/d$ è un divisore di $n$. □

Osservazione 5.7

Per ogni numero naturale $n \ge 2$, se $d > \sqrt{n}$ allora $n/d < \sqrt{n}$.

Dimostrazione

Se $d > \sqrt{n}$, dividendo $n$ per entrambi i membri di questa disuguaglianza otteniamo

\[ \frac{n}{d} < \frac{n}{\sqrt{n}} = \sqrt{n}. \]

Quindi $n/d$ è minore di $\sqrt{n}$. □

Corollario 5.8

Ogni numero naturale composto $n \ge 2$ ha un divisore $d$ con $2 \le d \le \lfloor \sqrt{n} \rfloor$. Equivalentemente, un numero naturale $n \ge 2$ è primo se e solo se nessun numero naturale in $\{2, 3, \dots, \lfloor \sqrt{n} \rfloor\}$ è un divisore di $n$.

Dimostrazione

Poiché $n$ è composto, ha un divisore $d$ con $2 \le d \le n-1$. Se $d \le \sqrt{n}$, allora $d \le \lfloor \sqrt{n} \rfloor$, perché $d$ è un numero naturale, e abbiamo finito. Altrimenti $d > \sqrt{n}$: per le due osservazioni precedenti, $n/d$ è un divisore di $n$ con $n/d < \sqrt{n}$, e $n/d \ge 2$ perché $d < n$. Quindi $n/d$ è un divisore di $n$ con $2 \le n/d \le \lfloor \sqrt{n} \rfloor$. □

Dalle osservazioni precedenti sappiamo che, per ogni numero naturale $n \ge 2$, se $d > \sqrt{n}$ è un divisore di $n$, allora anche $n/d$ è un divisore di $n$ e $n/d < \sqrt{n}$. Ne segue che ogni divisore di $n$ maggiore di $\sqrt{n}$ è accoppiato a un divisore di $n$ minore di $\sqrt{n}$. Quindi, se $n$ ha un qualche divisore (diverso da $1$ e da $n$), almeno uno di essi deve essere $\le \sqrt{n}$.

Esempio 5.3: illustrazione della proprietà

Consideriamo $n = 36$: $\sqrt{36} = 6$. I divisori di $36$ diversi da $1$ e da $36$ sono $2, 3, 4, 6, 9, 12, 18$.

divisore $d > \sqrt{36}$	divisore accoppiato $36/d < \sqrt{36}$
$9$	$36/9 = 4$
$12$	$36/12 = 3$
$18$	$36/18 = 2$

Ogni divisore $> 6$ è accoppiato a un divisore $< 6$; il divisore $6 = \sqrt{36}$ è accoppiato con se stesso.

Per il corollario, il ciclo dell'algoritmo di base può fermarsi a $\lfloor \sqrt{n} \rfloor$ invece che a $\lfloor n/2 \rfloor$.
Pseudocodice dell'algoritmo Primality Test (test di primalità):

Algoritmo: PrimalityTest

Input: Un numero naturale $n$

Output: true se $n$ è primo, false altrimenti

1function PrimalityTest(n)

2if $n < 2$ then

3return false// 0 e 1 non sono primi

4end

5$d := 2$

6while $d \le \lfloor\sqrt{n}\rfloor$ do

7if $n \bmod d = 0$ then

8return false// $d$ divide $n$: non primo

9end

10$d \leftarrow d + 1$

11end

12return true// Nessun divisore trovato: $n$ è primo

13end

Esegui in Colab:Python C++Java

Spiegazione dell'algoritmo:
- I numeri minori di $2$ non sono primi per definizione.
- Il ciclo prova ogni candidato divisore $d$ da $2$ fino a $\lfloor\sqrt{n}\rfloor$.
- Se $d$ divide $n$ (cioè $n \bmod d = 0$), la funzione restituisce subito false.
- Se il ciclo termina senza trovare alcun divisore, allora, per il corollario, $n$ è primo e la funzione restituisce true.
- Per $n = 2$ e $n = 3$ si ha $\lfloor \sqrt{n} \rfloor = 1 < 2$: il ciclo non viene eseguito e la funzione restituisce true.

Esempio 5.4: test di primalità

Verifica $n = 36$: $\lfloor\sqrt{36}\rfloor = 6$

$d$ $36 \bmod d$ azione

$2$ $0$ restituisce false

36 non è primo ($36 = 2 \cdot 18$).
Verifica $n = 29$: $\lfloor\sqrt{29}\rfloor = 5$

$d$ $29 \bmod d$ azione

$2$ $1 \ne 0$ continua

$3$ $2 \ne 0$ continua

$4$ $1 \ne 0$ continua

$5$ $4 \ne 0$ continua

Il ciclo termina. Restituisce true: 29 è primo.
Verifica $n = 25$: $\lfloor\sqrt{25}\rfloor = 5$

$d$ $25 \bmod d$ azione

$2$ $1 \ne 0$ continua

$3$ $1 \ne 0$ continua

$4$ $1 \ne 0$ continua

$5$ $0$ restituisce false

25 non è primo ($25 = 5 \cdot 5$).

Per il numero primo $29$ l'algoritmo prova $4$ candidati, mentre l'algoritmo di base ne prova $13$.

Punti chiave.

I divisori di $n$ si presentano a coppie $d$ e $n/d$, e in ogni coppia uno dei due numeri è al più $\sqrt{n}$.
Quindi $n \ge 2$ è primo se e solo se nessun numero naturale in $\{2, 3, \dots, \lfloor \sqrt{n} \rfloor\}$ lo divide.
Il Primality Test esegue al più $\lfloor \sqrt{n} \rfloor - 1$ iterazioni, invece delle $\lfloor n/2 \rfloor - 1$ iterazioni dell'algoritmo di base.

5.3 Crivello di Eratostene¶

Il Primality Test risponde alla domanda per un solo numero. Quando servono tutti i numeri primi fino a $n$, chiamarlo su $2, 3, \dots, n$ ripete molte divisioni; il crivello lavora al contrario: invece di cercare i divisori di ciascun numero, cancella i multipli di ciascun primo.

Dato un numero naturale $n$, consideriamo il problema di determinare tutti i numeri primi minori o uguali a $n$.

Il crivello di Eratostene è un algoritmo antico (attribuito al matematico greco Eratostene di Cirene, ca. 276–194 a.C.) che calcola tutti i numeri primi fino a un numero naturale $n$.
L'idea chiave è partire con tutti i numeri naturali da $2$ a $n$ marcati come potenzialmente primi, e poi marcare iterativamente come composti i multipli di ciascun primo.

Definizione 5.9: multiplo

Un numero naturale $m$ è un multiplo di un numero naturale $p \ge 1$ se esiste un numero naturale $k$ tale che $m = k \; p$:

\[ \text{$m$ è un multiplo di $p$} \quad \Longleftrightarrow \quad \exists\, k \in \N,\ m = k \; p \]

o, equivalentemente, se $m \bmod p = 0$.

La prima osservazione dice da dove può partire la marcatura dei multipli di $p$.

Osservazione 5.10

Per ogni numero naturale $p \ge 2$, se un numero naturale $m$ è un multiplo di $p$ con $p < m < p^2$, allora $m$ ha un divisore $d$ con $2 \le d < p$.

Dimostrazione

Poiché $m$ è un multiplo di $p$, esiste un numero naturale $d$ tale che $m = d \; p$. Allora $d$ è un divisore di $m$.

Inoltre, poiché $m > p$ e $m = d \; p$, si ha $d \ge 2$. Poiché $m < p^2$ e $m = d \; p$, si ha $d < p$. Quindi $2 \le d < p$. □

Dall'osservazione precedente, per ogni primo $p$ e ogni multiplo $m$ di $p$ con $p < m < p^2$, il numero $m$ ha un divisore $d$ con $2 \le d < p$. Quindi $m$ ha anche un divisore primo $q$ con $2 \le q < p$, ed era perciò già stato marcato come composto quando è stato elaborato $q$. Dunque, nel marcare i multipli di $p$, si può partire da $p^2$.

Esempio 5.6: illustrazione della proprietà

Sia $p = 5$. I suoi multipli compresi tra $p$ e $p^2 = 25$ sono $m = 10, 15, 20$.

multiplo $m$	$m = d \cdot p$	divisore $d < p$	già marcato quando
$10$	$10 = 2 \cdot 5$	$d = 2$	$p = 2$ (da $j = 4$, passo $2$)
$15$	$15 = 3 \cdot 5$	$d = 3$	$p = 3$ (da $j = 9$, passo $3$)
$20$	$20 = 4 \cdot 5$	$d = 4$	$p = 2$ (da $j = 4$, passo $2$)

Il numero $20$ ha il divisore $d = 4$, che non è primo, e anche il divisore primo $2$, che lo ha marcato. Il multiplo successivo è $25 = 5 \cdot 5 = p^2$, che non è stato marcato da nessun primo precedente. Quindi, per $p = 5$, si può iniziare a marcare i numeri da $25$.

La seconda osservazione dice dove può fermarsi il ciclo esterno su $p$.

Osservazione 5.11

Per ogni numero naturale $n \ge 2$, ogni numero naturale composto $m \le n$ ha un divisore primo $q$ con $q \le \lfloor \sqrt{n} \rfloor$.

Dimostrazione

Per il corollario della sezione «Test di primalità», $m$ ha un divisore $d$ con $2 \le d \le \lfloor \sqrt{m} \rfloor \le \lfloor \sqrt{n} \rfloor$. Sia $q$ il più piccolo divisore di $m$ con $q \ge 2$; allora $q \le d \le \lfloor \sqrt{n} \rfloor$. Il numero $q$ è primo: se $q$ avesse un divisore $c$ con $2 \le c < q$, allora $c$ sarebbe anche un divisore di $m$ (da $q = k_1 c$ e $m = k_2 q$ si ottiene $m = k_2 k_1 c$), contro la scelta di $q$ come il più piccolo. □

Quindi, dopo che sono stati marcati i multipli di tutti i primi $p \le \lfloor \sqrt{n} \rfloor$, ogni numero composto fino a $n$ è marcato, e il ciclo esterno può fermarsi.
Pseudocodice del crivello di Eratostene:

Algoritmo: SieveOfEratosthenes

Input: Un numero naturale $n \ge 1$

Output: Un array booleano $prime[1..n]$ dove $prime[i] = 1$ se e solo se $i$ è primo

1function SieveOfEratosthenes($n$)

2$prime := \text{new array}[1..n]$// dichiara l'array booleano

3$prime \leftarrow 1$// inizializza tutti gli elementi a 1

4$prime[1] \leftarrow 0$// 1 non è primo

5$p := 2$

6while $p \le \lfloor\sqrt{n}\rfloor$ do

7if $prime[p] = 1$ then

8$j := p^2$

9while $j \le n$ do

10$prime[j] \leftarrow 0$// $j$ non è primo

11$j \leftarrow j + p$

12end

13end

14$p \leftarrow p + 1$

15end

16return $prime$

17end

Esegui in Colab:Python C++Java

Spiegazione dell'algoritmo:
- L'array $prime$ viene dichiarato e tutti i suoi elementi sono inizializzati a $1$; l'elemento $prime[1]$ viene subito posto a $0$, poiché $1$ non è primo.
- Il ciclo esterno scorre ogni candidato primo $p$ da $2$ fino a $\lfloor\sqrt{n}\rfloor$.
- Se $prime[p] = 1$, allora $p$ è primo (un $p$ composto sarebbe stato marcato dal suo più piccolo divisore primo), e tutti i suoi multipli a partire da $p^2$ sono posti a $0$.
- Il ciclo interno parte da $p^2$ perché tutti i multipli più piccoli $2p, 3p, \ldots, (p{-}1)p$ sono già stati posti a $0$ nell'elaborare i primi più piccoli $2, 3, 5, 7, \ldots$.
- Dopo l'esecuzione dell'algoritmo, $prime[i] = 1$ se e solo se $i$ è primo.

Esempio 5.7: crivello di Eratostene ($n=10$)

Con $n=10$ ($\lfloor\sqrt{10}\rfloor = 3$), ogni riga mostra lo stato dell'array $prime[1..10]$ dopo l'assegnamento $prime[j] \leftarrow 0$. Le celle blu indicano gli elementi appena posti a $0$; le celle rosse indicano il valore corrente di $p$.

		$prime[1..10]$
$p$	$j$	1	2	3	4	5	6	7	8	9	10	azione
$-$	$-$	0	1	1	1	1	1	1	1	1	1	inizializzazione
2	4	0	1	1	0	1	1	1	1	1	1	$prime[4] \leftarrow 0$
	6	0	1	1	0	1	0	1	1	1	1	$prime[6] \leftarrow 0$
	8	0	1	1	0	1	0	1	0	1	1	$prime[8] \leftarrow 0$
	10	0	1	1	0	1	0	1	0	1	0	$prime[10] \leftarrow 0$
	12											$j = 12 > 10$: arresto
3	9	0	1	1	0	1	0	1	0	0	0	$prime[9] \leftarrow 0$
	12											$j = 12 > 10$: arresto
Il ciclo esterno termina: $p = 4 > \lfloor\sqrt{10}\rfloor = 3$.

Risultato: i numeri primi $\le 10$ sono $2,\ 3,\ 5,\ 7$.

Esempio 5.8: crivello di Eratostene ($n=20$)

Con $n=20$ ($\lfloor\sqrt{20}\rfloor = 4$), ogni riga mostra lo stato dell'array $prime[1..20]$ dopo l'assegnamento $prime[j] \leftarrow 0$. Celle blu: elemento appena posto a $0$; celle rosse: valore corrente di $p$. Quando l'elemento è già $0$, l'assegnamento non modifica l'array.

		$prime[1..20]$
$p$	$j$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	azione
$-$	$-$	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	inizializzazione
2	4	0	1	1	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	$prime[4] \leftarrow 0$
	6	0	1	1	0	1	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	$prime[6] \leftarrow 0$
	8	0	1	1	0	1	0	1	0	1	1	1	1	1	1	1	1	1	1	1	1	$prime[8] \leftarrow 0$
	10	0	1	1	0	1	0	1	0	1	0	1	1	1	1	1	1	1	1	1	1	$prime[10] \leftarrow 0$
	12	0	1	1	0	1	0	1	0	1	0	1	0	1	1	1	1	1	1	1	1	$prime[12] \leftarrow 0$
	14	0	1	1	0	1	0	1	0	1	0	1	0	1	0	1	1	1	1	1	1	$prime[14] \leftarrow 0$
	16	0	1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	1	1	1	$prime[16] \leftarrow 0$
	18	0	1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	1	$prime[18] \leftarrow 0$
	20	0	1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	$prime[20] \leftarrow 0$
	22																					$j = 22 > 20$: arresto
3	9	0	1	1	0	1	0	1	0	0	0	1	0	1	0	1	0	1	0	1	0	$prime[9] \leftarrow 0$
	12	0	1	1	0	1	0	1	0	0	0	1	0	1	0	1	0	1	0	1	0	$prime[12] \leftarrow 0$ (già $0$)
	15	0	1	1	0	1	0	1	0	0	0	1	0	1	0	0	0	1	0	1	0	$prime[15] \leftarrow 0$
	18	0	1	1	0	1	0	1	0	0	0	1	0	1	0	0	0	1	0	1	0	$prime[18] \leftarrow 0$ (già $0$)
	21																					$j = 21 > 20$: arresto
4																						$prime[4] = 0$: salta
Il ciclo esterno termina: $p = 5 > \lfloor\sqrt{20}\rfloor = 4$.

Risultato: i numeri primi $\le 20$ sono $2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19$.

Punti chiave.

Il crivello non divide: marca come composti i multipli di ciascun primo $p$.
La marcatura dei multipli di $p$ parte da $p^2$: i multipli più piccoli hanno un divisore primo più piccolo e sono già marcati.
Il ciclo esterno si ferma a $\lfloor \sqrt{n} \rfloor$: ogni numero composto fino a $n$ ha un divisore primo non maggiore di $\lfloor \sqrt{n} \rfloor$.

5.4 Massimo comun divisore¶

L'ultimo algoritmo del capitolo tratta due numeri alla volta: cerchiamo i divisori che hanno in comune.

Definizione 5.12: divisore comune e massimo comun divisore

Siano $n, m$ due numeri naturali con $n, m \ge 1$.

Un numero naturale $d \ge 1$ è un divisore comune di $n$ e $m$ se $d$ è un divisore sia di $n$ sia di $m$, cioè se esistono numeri naturali $k_1, k_2$ tali che

\[ n = k_1 \; d \qquad \text{e} \qquad m = k_2 \; d. \]

Equivalentemente, $n \bmod d = 0$ e $m \bmod d = 0$.
Il massimo comun divisore di $n$ e $m$, indicato con $\gcd(n, m)$, è il più grande divisore comune di $n$ e $m$.

Il massimo comun divisore esiste sempre: $1$ è un divisore comune, e ogni divisore comune è al più $\min\{n, m\}$.
Per esempio, i divisori comuni di $48$ e $18$ sono $1, 2, 3, 6$, quindi $\gcd(48, 18) = 6$.

Dati due numeri naturali $n, m$ con $n, m \ge 1$, consideriamo il problema di calcolare il loro massimo comun divisore.

L'osservazione seguente sostituisce la coppia $(n, m)$ con una coppia di numeri più piccoli che ha lo stesso massimo comun divisore.

Osservazione 5.13

Per ogni coppia di numeri naturali $n \ge 1$ e $m \ge 1$,

\[ \gcd(n, m) = \gcd(m,\ n \bmod m). \]

Dimostrazione

Sia $q = \lfloor n/m \rfloor$, in modo che $n = q m + (n \bmod m)$.

Sia $d_1$ un divisore comune di $n$ e $m$. Allora esistono numeri naturali $k_1, k_2$ tali che

\[ n = k_1 d_1 \qquad \text{e} \qquad m = k_2 d_1. \]

Poiché $n \bmod m = n - qm$, otteniamo

\[ n \bmod m = (k_1 - qk_2)\,d_1, \]

dove $k_1 - q k_2 \ge 0$ perché $n \bmod m \ge 0$. Quindi $d_1$ è anche un divisore di $n \bmod m$. Perciò $d_1$ è un divisore comune di $m$ e $n \bmod m$.

Viceversa, sia $d_2$ un divisore comune di $m$ e $n \bmod m$. Allora esistono numeri naturali $k_1, k_2$ tali che

\[ m = k_1 d_2 \qquad \text{e} \qquad n \bmod m = k_2 d_2. \]

Poiché $n = qm + (n \bmod m)$, otteniamo

\[ n = (qk_1 + k_2)\,d_2, \]

quindi $d_2$ è anche un divisore di $n$. Perciò $d_2$ è un divisore comune di $n$ e $m$.

Dunque $n$ e $m$ hanno esattamente gli stessi divisori comuni di $m$ e $n \bmod m$, e quindi

\[ \gcd(n,m)=\gcd(m,\,n \bmod m). \]

Nel membro di destra, $\gcd(m, 0)$ è inteso come il più grande divisore di $m$ (ogni $d \ge 1$ divide $0 = 0 \cdot d$), cioè $m$ stesso. □

5.4.1 Algoritmo di Euclide¶

L'algoritmo di Euclide (attribuito all'antico matematico greco Euclide, ca. 300 a.C.) calcola $\gcd(n, m)$ in modo efficiente sostituendo ripetutamente la coppia $(n,m)$ con $(m,\ n \bmod m)$.
L'algoritmo non richiede $n \ge m$: se $n < m$, allora $n \bmod m = n$, e la prima sostituzione scambia semplicemente i due numeri, trasformando $(n, m)$ in $(m, n)$.

Per l'osservazione precedente, sostituire $(n,m)$ con $(m,\ n \bmod m)$ non cambia il massimo comun divisore.
Poiché $n \bmod m < m$, il secondo argomento decresce strettamente a ogni sostituzione.
Dunque l'algoritmo termina quando il resto diventa $0$; a quel punto il massimo comun divisore è l'altro argomento:

\[ \gcd(n,0)=n. \]

Pseudocodice dell'algoritmo di Euclide:

Algoritmo: EuclideanAlgorithm

Input: Due numeri naturali $n, m \ge 1$

Output: $\gcd(n, m)$

1function EuclideanAlgorithm($n$, $m$)

2while $m \ne 0$ do

3$r := n \bmod m$

4$n \leftarrow m$

5$m \leftarrow r$

6end

7return $n$// $m = 0$: $n$ è il MCD

8end

Esegui in Colab:Python C++Java

Spiegazione dell'algoritmo:
- A ogni passo, $(n, m)$ viene sostituita da $(m,\ n \bmod m)$.
- Per l'osservazione precedente, questa sostituzione conserva il valore di $\gcd(n,m)$: indicando con $n_0$ e $m_0$ i valori in input, a ogni iterazione $\gcd(n, m) = \gcd(n_0, m_0)$.
- Poiché $n \bmod m < m$, il valore di $m$ decresce strettamente a ogni iterazione, quindi l'algoritmo termina.
- Quando $m = 0$, l'uguaglianza $\gcd(n, m) = \gcd(n_0, m_0)$ insieme a $\gcd(n, 0) = n$ dà il risultato.

Esempio 5.10: calcolo del MCD

Calcoliamo $\gcd(48, 18)$:

passo	$n$	$m$	$r = n \bmod m$
$1$	$48$	$18$	$48 \bmod 18 = 12$
$2$	$18$	$12$	$18 \bmod 12 = 6$
$3$	$12$	$6$	$12 \bmod 6 = 0$
$4$	$6$	$0$	— (il ciclo termina)

Risultato: $\gcd(48, 18) = 6$.

Calcoliamo $\gcd(252, 105)$:

passo	$n$	$m$	$r = n \bmod m$
$1$	$252$	$105$	$252 \bmod 105 = 42$
$2$	$105$	$42$	$105 \bmod 42 = 21$
$3$	$42$	$21$	$42 \bmod 21 = 0$
$4$	$21$	$0$	— (il ciclo termina)

Risultato: $\gcd(252, 105) = 21$.

5.4.2 Coprimalità¶

Definizione 5.14: numeri coprimi

Due numeri naturali $n, m \ge 1$ si dicono coprimi (o primi tra loro) se non hanno alcun divisore comune diverso da $1$:

\[ n \text{ e } m \text{ sono coprimi} \quad\Longleftrightarrow\quad \gcd(n, m) = 1 . \]

Poiché l'algoritmo di Euclide calcola $\gcd(n,m)$, per verificare la coprimalità basta chiamare l'algoritmo e controllare se il risultato è uguale a $1$.

Esempio 5.11: test di coprimalità

Calcoliamo $\gcd(35, 12)$: l'algoritmo di Euclide restituisce $1$. Quindi $35$ e $12$ sono coprimi.
Calcoliamo $\gcd(48, 18)$: l'algoritmo di Euclide restituisce $6$. Quindi $48$ e $18$ non sono coprimi.

Punti chiave.

Le coppie $(n, m)$ e $(m,\ n \bmod m)$ hanno gli stessi divisori comuni, quindi lo stesso massimo comun divisore.
L'algoritmo di Euclide ripete la sostituzione finché il secondo numero è $0$, e restituisce il primo, poiché $\gcd(n, 0) = n$.
Due numeri sono coprimi se e solo se l'algoritmo di Euclide restituisce $1$.

Esercizi su questo capitolo: Algoritmi numerici

Laboratorio interattivo¶

L'algoritmo del capitolo, un passo alla volta: muovi i cursori e premi ▶. Lo stesso grafico a tutta pagina, con gli altri del corso, è nel laboratorio interattivo.

iterazione \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	cifra
\(1\)	\(7\)	\(7/2\)	\(3\)	\(1\)	\(d[1] = d_{0}\) (meno significativa)
\(2\)	\(3\)	\(3/2\)	\(1\)	\(1\)	\(d[2] = d_{1}\)
\(3\)	\(1\)	\(1/2\)	\(0\)	\(1\)	\(d[3] = d_{2}\) (più significativa)

iterazione \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	cifra
\(1\)	\(8\)	\(8/2\)	\(4\)	\(0\)	\(d[1] = d_{0}\) (meno significativa)
\(2\)	\(4\)	\(4/2\)	\(2\)	\(0\)	\(d[2] = d_{1}\)
\(3\)	\(2\)	\(2/2\)	\(1\)	\(0\)	\(d[3] = d_{2}\)
\(4\)	\(1\)	\(1/2\)	\(0\)	\(1\)	\(d[4] = d_{3}\) (più significativa)

iterazione \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	cifra
\(1\)	\(25\)	\(25/3\)	\(8\)	\(1\)	\(d[1] = d_{0}\) (meno significativa)
\(2\)	\(8\)	\(8/3\)	\(2\)	\(2\)	\(d[2] = d_{1}\)
\(3\)	\(2\)	\(2/3\)	\(0\)	\(2\)	\(d[3] = d_{2}\) (più significativa)

iterazione \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	cifra
\(1\)	\(100\)	\(100/8\)	\(12\)	\(4\)	\(d[1] = d_{0}\) (meno significativa)
\(2\)	\(12\)	\(12/8\)	\(1\)	\(4\)	\(d[2] = d_{1}\)
\(3\)	\(1\)	\(1/8\)	\(0\)	\(1\)	\(d[3] = d_{2}\) (più significativa)

divisore \(d > \sqrt{36}\)	divisore accoppiato \(36/d < \sqrt{36}\)
\(9\)	\(36/9 = 4\)
\(12\)	\(36/12 = 3\)
\(18\)	\(36/18 = 2\)

\(d\)	\(36 \bmod d\)	azione
\(2\)	\(0\)	restituisce `false`
36 non è primo (\(36 = 2 \cdot 18\)).

\(d\)	\(29 \bmod d\)	azione
\(2\)	\(1 \ne 0\)	continua
\(3\)	\(2 \ne 0\)	continua
\(4\)	\(1 \ne 0\)	continua
\(5\)	\(4 \ne 0\)	continua
Il ciclo termina. Restituisce `true`: 29 è primo.

multiplo \(m\)	\(m = d \cdot p\)	divisore \(d < p\)	già marcato quando
\(10\)	\(10 = 2 \cdot 5\)	\(d = 2\)	\(p = 2\) (da \(j = 4\), passo \(2\))
\(15\)	\(15 = 3 \cdot 5\)	\(d = 3\)	\(p = 3\) (da \(j = 9\), passo \(3\))
\(20\)	\(20 = 4 \cdot 5\)	\(d = 4\)	\(p = 2\) (da \(j = 4\), passo \(2\))

		\(prime[1..10]\)
\(p\)	\(j\)	1	2	3	4	5	6	7	8	9	10	azione
\(-\)	\(-\)	0	1	1	1	1	1	1	1	1	1	inizializzazione
2	4	0	1	1	0	1	1	1	1	1	1	\(prime[4] \leftarrow 0\)
	6	0	1	1	0	1	0	1	1	1	1	\(prime[6] \leftarrow 0\)
	8	0	1	1	0	1	0	1	0	1	1	\(prime[8] \leftarrow 0\)
	10	0	1	1	0	1	0	1	0	1	0	\(prime[10] \leftarrow 0\)
	12											\(j = 12 > 10\): arresto
3	9	0	1	1	0	1	0	1	0	0	0	\(prime[9] \leftarrow 0\)
	12											\(j = 12 > 10\): arresto
Il ciclo esterno termina: \(p = 4 > \lfloor\sqrt{10}\rfloor = 3\).

passo	\(n\)	\(m\)	\(r = n \bmod m\)
\(1\)	\(48\)	\(18\)	\(48 \bmod 18 = 12\)
\(2\)	\(18\)	\(12\)	\(18 \bmod 12 = 6\)
\(3\)	\(12\)	\(6\)	\(12 \bmod 6 = 0\)
\(4\)	\(6\)	\(0\)	— (il ciclo termina)

passo	\(n\)	\(m\)	\(r = n \bmod m\)
\(1\)	\(252\)	\(105\)	\(252 \bmod 105 = 42\)
\(2\)	\(105\)	\(42\)	\(105 \bmod 42 = 21\)
\(3\)	\(42\)	\(21\)	\(42 \bmod 21 = 0\)
\(4\)	\(21\)	\(0\)	— (il ciclo termina)

Algoritmi numerici¶

Introduzione¶

5.1 Cambio di base¶

5.1.1 Divisione con resto¶

5.1.2 L'algoritmo¶

5.2 Test di primalità¶

5.2.1 Un primo algoritmo¶

5.2.2 Provare i divisori fino a \(\sqrt{n}\)¶

5.3 Crivello di Eratostene¶

5.4 Massimo comun divisore¶

5.4.1 Algoritmo di Euclide¶

5.4.2 Coprimalità¶

Laboratorio interattivo¶