Complessità: primo

di

Vedi 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:                        # c7
    print(n, "NON è primo")  # c8

T(2) = c_1+c_2+c_3+c_5+c_6 = 5
T(3) = c_1+c_2+(c_3+c_4)+c_3+c_5+c_6 = 2+5 = 7
T(4) = T(6) = T(8) = … = c_1+c_2+c_3+c_5+c_7+c_8 = 6
T(5) = c_1+c_2+3\cdot(c_3+c_4)+c_3+c_5+c_6 = 3\cdot 2+5 = 11
T(7) = c_1+c_2+5\cdot(c_3+c_4)+c_3+c_5+c_6 = 5\cdot 2+5 = 15
T(9) = T(15) = T(21) = … = c_1+c_2+(c_3+c_4)+c_3+c_5+c_7+c_8 = 2+6 = 8
T(11) = c_1+c_2+9\cdot(c_3+c_4)+c_3+c_5+c_6 = 9\cdot 2+5 = 23
…

Quindi

nT(n)?
25Caso ottimo
4, 6, 8, 10, …6
9, 15, 21, 27, …8
……
3, 5, 7, 11, … (n primo)2n+1Caso pessimo

L’algoritmo che decide se un numero n è primo, con il metodo delle divisioni successive, ha una complessità in tempo lineare.

2

I multipli di 2 non sono primi…

n = int(input("n = "))           # c1
if(n == 2):                      # c2
    print(n, "è primo")          # c3
elif(n%2 == 0):                  # c4
    print(n, "NON è primo")      # c5
else:                            # c6
    i = 3                        # c7
    while(n%i != 0):             # c8
        i = i+2                  # c9      
    if(i == n):                  # c10   
        print(n, "è primo")      # c11
    else:                        # c12
        print(n, "NON è primo")  # c13

T(2) = c_1+c_2+c_3 = 3
T(3) = c_1+c_2+c_4+c_6+c_7+c_8+c_{10}+c_{11} = 8
T(4) = T(6) = T(8) = … = c_1+c_2+c_4+c_5 = 4
T(5) = c_1+c_2+c_4+c_6+c_7+c_8+(c_8+c_9)+c_{10}+c_{11} = 2+8 = 10
T(7) = c_1+c_2+c_4+c_6+c_7+c_8+2\cdot(c_8+c_9)+c_{10}+c_{11} = 2\cdot 2+8 = 12
T(9) = c_1+c_2+c_4+c_6+c_7+c_8+c_{10}+c_{12}+c_{13} = 9
T(11) = c_1+c_2+c_4+c_6+c_7+c_8+4\cdot(c_8+c_9)+c_{10}+c_{11} = 4\cdot 2+8 = 16
…

Quindi

nT(n)?
23Caso ottimo
4, 6, 8, 10, …4
9, 15, 21, 27, …9
……
3, 5, 7, 11, … (n primo)n+5Caso pessimo

L’algoritmo che decide se un numero n è primo, con il metodo …, ha una complessità in tempo lineare.
Il coefficiente moltiplicativo è diminuito…

3

Non è necessario fare le divisioni da 2 a n-1, si può fermare il while a m = \lfloor \sqrt{n} \rfloor.

import math

n = int(input("n = "))             # c1
if(n == 2):                        # c2
    print(n, "è primo")            # c3
elif(n%2 == 0):                    # c4
    print(n, "NON è primo")        # c5
else:                              # c6
    m = math.floor(math.sqrt(n))   # c7 
    i = 3                          # c8
    while(i <= m) and (n%i != 0):  # c9
        i = i+2                    # c10      
    if(i > m):                     # c11   
        print(n, "è primo")        # c12
    else:                          # c13
        print(n, "NON è primo")    # c14

L’algoritmo che decide se un numero n è primo, con il metodo …, ha una complessità in tempo sottolineare (polinomiale con esponente 1/2).

Esistono algoritmi con prestazioni migliori… (vedi Wikipedia)