Crible d'Ératosthène

Exercice d'optimisation

On suppose que vous avez déjà résolu la première version du Crible d'Ératosthène. On propose ici de montrer quelques petites améliorations. Un autre problème sera consacré pour d'autres améliorations importantes.

Objectif : Construire rapidement un tableau de primalité des entiers de \(0\) inclus à \(n\) inclus.

Méthode : On peut utiliser le crible d'Ératosthène. Vous avez déjà rencontré une première version qui ressemble à :

🐍 Script Python

def eratosthene(n):
    crible = [True] * (n + 1)
    crible[0] = False  # 0 n'est pas premier
    if n > 0:
        crible[1] = False  # 1 n'est pas premier
    for p in range(2, n + 1):
        if crible[p]:
            # p est premier
            for kp in range(2*p, n + 1, p):
                # kp est un multiple de p, donc non premier
                crible[kp] = False
    return crible

On peut vérifier ceci avec le test ci-dessous

🐍 Console Python

>>> limite = 20
>>> primalite = eratosthene(limite)
>>> primalite_brute = [est_premier(i) for i in range(limite + 1)]
>>> primalite == primalite_brute
True

L'objectif de l'exercice est d'améliorer la fonction eratosthene en suivant les conseils suivants :

1. Remplacer la ligne for p in range(2, n + 1): par une structure avec une boucle while.
2. Remplacer la ligne for kp in range(2*p, n + 1, p): par for kp in range(p*p, n + 1, p):, en effet les multiples de \(2p\) inclus à \(p^2\) exclu ont déjà été cochés, on peut donc commencer à \(p^2\).
3. En déduire que quand \(p×p > n\) il n'y plus de nouveaux multiples à cocher. Ils ont tous déjà été cochés. C'est une propriété mathématique : « Si un entier \(n\) est composé, alors il possède un diviseur premier inférieur ou égal à \(\sqrt{n}\) ». Modifier la boucle while en conséquence.
4. Tester votre fonction eratosthene_V2 en la confrontant à eratosthene et à une méthode par force brute.

Génération des nombres premiers

Quand vous aurez terminé, vous pourrez tester une astuce avec Python pour générer la liste des nombres premiers à partir du tableau de booléens primalite.

Lire la documentation au sujet de itertools.compress

🐍 Console Python

>>> from itertools import compress
>>> limite = 20
>>> primalite = eratosthene(limite)
>>> list(compress(range(limite + 1), primalite))
[2, 3, 5, 7, 11, 13, 17 ,19]

Pour tester cela, construire une fonction telle que somme_premiers(n) renvoie la somme des nombres premiers jusqu'à \(n\).

Exemples

🐍 Console Python

>>> somme_premiers(5)
10
>>> somme_premiers(20)
77

###

Lancer # testsbksl-nlbksl-nlassert sommepy-undpremiers(5) == 10bksl-nlassert sommepy-undpremiers(20) == 77bksl-nlbksl-nlbksl-nl# autres testsbksl-nlbksl-nlbksl-nldef ESTpy-undpremier(n):bksl-nl if n < 2:bksl-nl return Falsebksl-nl for d in range(2, n):bksl-nl # 1 < d < nbksl-nl if n % d == 0:bksl-nl # d est un diviseur de n, autre que 1 et nbksl-nl return Falsebksl-nl return Truebksl-nlbksl-nlbksl-nldef SOMMEpy-undpremiers(n):bksl-nl return sum(p for p in range(n + 1) if ESTpy-undpremier(p))bksl-nlbksl-nlbksl-nlfor n in range(100):bksl-nl attendu = SOMMEpy-undpremiers(n)bksl-nl assert sommepy-undpremiers(n) == attendu, f"Erreur avec n = {n}"bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def sommepy-undpremiers(n):bksl-nl ...bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert sommepy-undpremiers(5) == 10bksl-nlassert sommepy-undpremiers(20) == 77bksl-nlbksl-nldef estpy-undpremier(n):bksl-nl if n < 2:bksl-nl return Falsebksl-nl for d in range(2, n):bksl-nl # 1 < d < nbksl-nl if n % d == 0:bksl-nl # d est un diviseur de n, autre que 1 et nbksl-nl return Falsebksl-nl return Truebksl-nlbksl-nlbksl-nldef eratosthene(n):bksl-nl crible = [True] py-str (n + 1)bksl-nl crible[0] = False # 0 n'est pas premierbksl-nl if n > 0:bksl-nl crible[1] = False # 1 n'est pas premierbksl-nl for p in range(2, n + 1):bksl-nl if crible[p]:bksl-nl # p est premierbksl-nl for kp in range(2 py-str p, n + 1, p):bksl-nl # kp est un multiple de p, donc non premierbksl-nl crible[kp] = Falsebksl-nl return criblebksl-nlbksl-nlbksl-nldef eratosthenepy-undV2(n):bksl-nl crible = [True] py-str (n + 1)bksl-nl crible[0] = False # 0 n'est pas premierbksl-nl if n > 0:bksl-nl crible[1] = False # 1 n'est pas premierbksl-nl p = 2bksl-nl while p py-str p <= n:bksl-nl if crible[p]:bksl-nl # p est premierbksl-nl for kp in range(p py-str p, n + 1, p):bksl-nl # kp est un multiple de p, donc non premierbksl-nl crible[kp] = Falsebksl-nl p += 1bksl-nl return criblebksl-nlbksl-nlbksl-nldef eratosthenepy-undV3(n):bksl-nl crible = bytearray([True]) py-str (n + 1)bksl-nl crible[0] = False # 0 n'est pas premierbksl-nl if n > 0:bksl-nl crible[1] = False # 1 n'est pas premierbksl-nl p = 2bksl-nl while p py-str p <= n:bksl-nl if crible[p]:bksl-nl crible[p py-str p : n + 1 : p] = bytearray([False]) py-str len(bksl-nl crible[p py-str p : n + 1 : p]bksl-nl )bksl-nl p += 1bksl-nl return criblebksl-nlbksl-nlbksl-nlfrom itertools import compressbksl-nlbksl-nlbksl-nldef sommepy-undpremiers(n):bksl-nl primalite = eratosthenepy-undV2(n)bksl-nl return sum(compress(range(n + 1), primalite))bksl-nlbksl-nl

A

Force brute

🐍 Script Python

def est_premier(n):
    if n < 2:
        return False
    for d in range(2, n):
        # 1 < d < n
        if n % d == 0:
            # d est un diviseur de n, autre que 1 et n
            return False
    return True

def crible_brute(limite):
    return [est_premier(i) for i in range(limite)]

Il s'agit d'une traduction directe de la définition.

Cette version est lente, en effet le cout du calcul pour est_premier(n) est dans le pire des cas de n tours de boucles. La somme des couts pour i allant de zéro jusqu'à la limite est importante.

Première version du crible

Vérifier globalement sur une tranche (de \(0\) à \(n\)), avec un bon algorithme, c'est plus efficace que de nombreuses réponses locales. C'est ça le principe du crible.

🐍 Script Python

def eratosthene(n):
    crible = [True] * (n + 1)
    crible[0] = False  # 0 n'est pas premier
    if n > 0:
        crible[1] = False  # 1 n'est pas premier
    for p in range(2, n + 1):
        if crible[p]:
            # p est premier
            for kp in range(2*p, n + 1, p):
                # kp est un multiple de p, donc non premier
                crible[kp] = False
    return crible

Cette version est à améliorer pour deux raisons :

1. for p in range(2, n + 1): ; on pourra vérifier qu'il n'y a rien de nouveau à cocher quand \(p^2 > n\)...
2. for kp in range(2*p, n + 1, p): ; on peut commencer à p*p au lieu de 2*p, les premiers multiples ont déjà été cochés.

Deuxième version

🐍 Script Python

def eratosthene_V2(n):
    crible = [True] * (n + 1)
    crible[0] = False  # 0 n'est pas premier
    if n > 0:
        crible[1] = False  # 1 n'est pas premier
    p = 2
    while p * p <= n:
        if crible[p]:
            # p est premier
            for kp in range(p*p, n + 1, p):
                # kp est un multiple de p, donc non premier
                crible[kp] = False
        p += 1
    return crible

La principale différence est que la boucle interne commence à \(p^2\), en effet les multiples précédents de \(p\) ont déjà été marqués comme composés.

On a alors remplacé la boucle externe par une boucle while qui s'arrête quand \(p^2\) atteint la limite \(n\).

Version hors programme NSI

Voici quelques astuces pour améliorer encore le crible.

Il faut connaitre l'utilisation des tranches (slice) avec Python.

🐍 Script Python

def eratosthene_V3(n):
    crible = bytearray([True]) * (n + 1)
    crible[0] = False  # 0 n'est pas premier
    if n > 0:
        crible[1] = False  # 1 n'est pas premier
    p = 2
    while p * p <= n:
        if crible[p]:
            crible[p*p:n + 1:p] = bytearray([False]) * len(crible[p*p:n + 1:p])
        p += 1
    return crible

1. Un booléen prend beaucoup de place en Python pour la quantité d'informations qu'il porte. Une liste de booléens accentue fortement cet effet. On utilise alors byterray qui fonctionne exactement comme une liste, mais ses éléments sont des entiers sur un octet seulement, au lieu de plusieurs pour un seul entier. Il y a un gain important en mémoire, donc en temps !
2. On remplace la boucle interne par une affectation d'une tranche par une autre tranche.

Il reste alors une autre bonne amélioration à mettre en place.

On peut calculer len(crible[p*p:n + 1:p]) en fonction de n et de p ; ce qui évite un parcours de cette tranche. C'est à vous de trouver la formule !

Pour rechercher encore l'optimisation, mais au prix d'un code plus lourd, on pourra créer une liste ne modélisant que les nombres impairs. On fera le crible directement sur cette liste qui prend deux fois moins de place ; c'est aussi deux fois plus rapide.

On pensera lors de la génération des nombres premiers à ajouter 2 au début. En effet, il n'est pas modélisé dans les entiers impairs.

Cette optimisation est laissée à titre d'exercice...

Et la suite ?

Il y aura un autre exercice pour travailler sur le crible segmenté.

Idée : faire un crible sur une tranche de \(a\) à \(b\) pour utiliser moins de mémoire, idéalement que tout tienne dans la mémoire cache qui est nettement plus rapide que la mémoire vive. Ensuite, on itère sur toutes les tranches d'un découpage des entiers jusqu'à \(n\).

Z

Vous ajouterez tous les tests utiles aux différentes étapes.