Aller au contenu

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
###
# testsbksl-nlbksl-nlassert sommepy-undpremiers(5) == 10bksl-nlassert sommepy-undpremiers(20) == 77bksl-nlbksl-nlbksl-nlbksl-nl# autres testsbksl-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-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 ∞/∞

def sommepy-undpremiers(n):bksl-nl ...bksl-nlbksl-nlbksl-nlbksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert sommepy-undpremiers(5) == 10bksl-nlassert sommepy-undpremiers(20) == 77bksl-nlbksl-nlNone

A

Z

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

Retour en haut de la page