Page 3 of 6
Osservazione: Se un numero N non è primo, allora esiste un suo divisore minore o uguale della radice quadrata di N (se non hai fede, clicca qui 
per la dimostrazione)
che significa? Significa che se arriviamo senza aver trovato un divisore di N, possiamo terminare la ricerca perché siamo certi che N è primo. Dunque, il valore finale sarà √N
La pseudocodifica della struttura iterativa sarà:
k=2
mentre(k <= √N){
...
k=k + 1
}
dove k è un indice candidato divisore di N.