n° 105

def est_premier(n):
    """Vrai si n est un nombre premier.

    Precondition  : n est un entier >= 0.
    Postcondition : le resultat vaut True si et seulement si n >= 2 et n n'a
                    pas d'autre diviseur que 1 et lui-meme.
    """
    assert n >= 0
    if n < 2:
        return False
    d = 2
    while d * d <= n:
        if n % d == 0:
            return False
        d = d + 1
    return True

Pourquoi $d\times d>n$ suffit. Si $n$ est composé, il s'écrit $n=d\times q$ avec $2\le d\le q$. Alors $d^2\le d\times q=n$, donc $d\le \sqrt{n}$ : tout nombre composé possède un diviseur inférieur ou égal à sa racine carrée. Si aucun diviseur n'a été trouvé jusque-là, il n'y en a pas du tout.

Le gain. La version naïve essaie $n-2$ diviseurs, la version arrêtée à la racine en essaie environ $\sqrt{n}$. Pour $n=1000003$, c'est $1000001$ divisions contre $1000$ : un facteur mille. Le coût passe de proportionnel à $n$ à proportionnel à $\sqrt{n}$ — et l'écart grandit avec $n$.

La vérification différentielle. On écrit la version naïve, dont on est sûr, et on compare :

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

for n in range(0, 3000):
    assert est_premier(n) == est_premier_naif(n)

Les $3000$ cas concordent. Contrôles : les premiers inférieurs à $100$ obtenus sont bien les $25$ attendus, de $2$ à $97$. Et $2026=2\times 1013$ n'est pas premier, tandis que $2027$ et $2029$ le sont.

Les cas limites qui comptent : $0$ et $1$ ne sont pas premiers — par définition, pas par accident. $2$ l'est, et c'est le seul premier pair : la boucle ne s'exécute pas ($2\times 2>2$) et la fonction rend True. $4$ est le plus petit cas où la boucle sert vraiment.