Nombre d'opérations et temps de calcul

# version A : on divise par tous les entiers jusqu'à n-1
# version B : on s'arrête dès que d*d > n

import time

def premier_A(n):
    for d in range(2, n):
        if n % d == 0:
            return False
    return True

def premier_B(n):
    d = 2
    while d * d <= n:
        if n % d == 0:
            return False
        d = d + 1
    return True

n = 1000003
debut = time.time()
print(premier_B(n), time.time() - debut)   # True, moins d'un millième de seconde

La version B effectue au plus $\sqrt{n}\approx 1000$ tours ; la version A en effectue près d'un million — mille fois plus.

Justification de l'arrêt à $\sqrt{n}$ : si $n=a\times b$ avec $a\le b$, alors $a\le \sqrt{n}$. Tout nombre composé possède donc un diviseur inférieur ou égal à sa racine carrée ; n'en avoir trouvé aucun suffit à conclure.

On touche ici à la complexité d'un algorithme : deux programmes justes ne se valent pas.