Pagina 206 del libro di testo
n = int(input("n = ")) # c1
i = 2 # c2
while(n%i != 0): # c3
i = i+1 # c4
if(i == n): # c5
print(n, "è primo") # c6
else:
print(n, "NON è primo") # c7
- T(2) = c1+c2+c3+c5+c7 = 5
- T(3) = c1+c2+(c3+c4)+c3+c5+c6 = 2*1+5 = 7
- T(4) = c1+c2+c3+c5+c7 = 5
- T(5) = c1+c2+(c3+c4)+(c3+c4)+(c3+c4)+c3+c5+c6 = 2*3+5
- T(6) = c1+c2+c3+c5+c7 = 5
…
Quindi
- Caso ottimo: n=2, T(2) = 5
- … oppure n pari: n=2*m, T(2*m) = 5
- Caso pessimo
- Se n è primo falliscono tutte le divisioni per i da 2 a n-1 e ha successo per i=n
- T(n) = 2*(n-2)+5 = 2*n-4+5 = 2*n+1
Il problema di decidere se un numero n è primo affrontato con l’algoritmo delle divisioni successive porta a una complessità in tempo lineare nel numero delle divisioni.
2
Non è necessario fare le divisioni da 2 a n-1, si può fermare il while a m = 
.
Il problema di decidere se un numero n è primo affrontato con l’algoritmo delle divisioni successive fino alla radice quadrata di n porta a una complessità in tempo polinomiale con esponente 1/2.
Esistono algoritmi con prestazioni migliori… (vedi Wikipedia)