Algoritmo dei numeri primi
Questo algoritmo è utile per verificare se un numero è un numero primo oppure no.
Cos'è un numero primo? E' un numero positivo divisibile soltanto per se stesso e per uno. I due divisori devono essere distinti, pertanto il numero 1 non è un numero primo.
Scorrendo l'algoritmo sui numeri interi da 1 a n, l'algoritmo permette anche di trovare i numeri primi dell'insieme.
Il diagramma a blocchi
In questo flow chart ho descritto il funzionamento dell'algoritmo.
Lo pseudocodice dell'algoritmo
Ecco lo pseudocodice dell'algoritmo
- class primo(n) {
- # non è un numero primo se
- if n<2 return false
- # è un numero primo se 2 o 3
- if (n=2) o (n=3) return true
- if n%2=0 return false
- if n%3=0 return false
- #dividi il numero per i numeri dispari da 3 in poi fino alla radice quadrata di n
- c=5
- limite=radice quadrata di n
- while (c <= limite)
- # se n è divisibile per c è un numero primo
- if n%c=0 return false
- c=c+2
- # a questo punto n è sicuramente un numero primo
- return true
- }
Un esempio pratico
L'algoritmo analizza il numero n=73.
Il numero 73 supera i controlli iniziali dalla riga 2 alla riga 7.
- 73 non è minore di zero
- il resto di 73/2 è 1
- il resto di 73/3 è 1
- 73 non è uguale a 2
- 73 non è uguale a 3
A questo punto, l'algoritmo controlla se esiste un numero dispari in grado di dividere il numero senza resto.
Non tutti però. Basta verificare i numeri dispari positivi e interi inferiori alla sua radice quadrata.
$$ \sqrt{73} =8.544 $$
Quindi il confronto va fatto sui numeri
$$ 1, 3, 5, 7 $$
Il numero 1 può essere eliminato perché qualsiasi numero è divisibile per 1
Il numero 3 può essere eliminato perché l'algoritmo ha già provato a dividere il numero per 3
Pertanto, il confronto deve essere fatto soltanto sui numeri
$$ 5, 7 $$
L'algoritmo divide il numero per la lista dei divisori (5,7) e verifica se il resto è uguale a zero
- il resto di 73/5 è 1
- il resto di 73/7 è 1
Non essendoci altri divisori, il numero 73 è sicuramente un numero primo.
