erathostene — Crible d’Érathostène optimisé en espace

Le crible d’Érathostène est un algorithme permettant d’énumérer tous les nombres premiers inférieurs à un certain nombre \(N\). Cette version l’améliore suivant deux aspects :

  1. Le nombre maximal n’a pas a être précisé au départ : les nombres premiers sont énumérés tant que l’utilisateur n’arrête pas le programme.
  2. La mémoire nécessaire est linéaire en le nombre de nombres premiers trouvés, et non pas en le plus grand nombre premier. La mémoire nécéssaire est donc en \(O\left(\frac{n}{\ln n}\right)\) au lieu de \(O(n)\) (où \(n\) est le plus grand nombre premier trouvé).

L’algorithme est décrit par la suite (Algorithme), et implémenté dans la fonction premiers().

Usage

Print primes numbers

usage: erathostene [-h] [-v]

Named Arguments

-v, --version show program’s version number and exit

This program prints prime numbers until it is killed.

Algorithme

Code source

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def premiers():
    """Itérateur des nombres premiers"""
    prochains = ListeTriee()
    yield 2
    yield 3
    prochains.push(3, 9)
    nombre = 5
    while True:
        premier, multiple = prochains.pop()
        while multiple != nombre:
            yield nombre
            prochains.push(nombre, nombre ** 2)
            nombre += 2
        nombre += 2
        prochains.push(premier, prochains.suivant(multiple, 2 * premier))

Algorithme d’Érathostène original

Le principe du crible d’Érathostène est :

  1. On considère une table de tous les nombres entiers naturels supérieurs (strictement) à 1, jusqu’à un certain \(N\).
  2. On prend le premier nombre de cette table : il est premier. On le supprime, et on supprime également de la table tous ses multiples.
  3. On recommence l’étape précédente jusqu’à épuisement de la liste.

Optimisation en espace

L’optimisation consiste en la chose suivante. On maintient une liste de couples \((p, m)\) (variable prochains), où \(p\) est un nombre premier, et \(m\) le prochain (nous verrons dans quel sens) de ses multiples. Ensuite, quand un nombre premier est trouvé, plutôt que de supprimer tous ses multiples de la table des entiers (qui ne sera donc pas utile ici), on ajoute à la liste prochains ce nombre, ainsi que son prochain multiple.

L’algorithme (de base : quelques optimisations seront apportées dans la section suivante) est donc le suivant :

  1. Initialisation : prochains contient le couple (2, 4), et nombre=3.
  2. On considère nombre :
  • S’il est une des clefs de la liste prochains, il est donc multiple d’un nombre premier : il n’est pas premier. On met à jour le couple \((premier, multiple)\) rencontré (en le remplaçant par le couple \((premier, multiple + premier)\)).
  • Sinon, nombre est premier. On l’affiche à l’utilisateur, et on ajoute un couple \((nombre, 2\times nombre)\) à la liste prochains.
  1. On ajoute 1 à nombre, et on recommence à l’étape 2.

Optimisations supplémentaires

Quelques optimisations sont mises en place.

  • Plutôt que de compter de 1 en 1, on remarque que 2 est premier, et on compte de 2 en 2, uniquement les nombres impairs (puisqu’aucuns des nombres pairs autre que 2 n’est premier). L’initialisation est changée également, et on ne considère que les multiples de nombres premiers impairs.
  • La liste prochains est triée : cela évite de la parcourir sans arrêt (mais il faut tout de même la parcourir pour ajouter de nouveaux éléments à la bonne place).
  • Le multiple du couple \((premier, multiple)\) n’est pas nécéssairement le prochain multiple de \(premier\) si cela n’est pas nécessaire. Par exemple, si prochains contient le couple \((3, 15)\), il n’est pas nécessaire d’ajouter \((5, 15)\) à la liste, puisque 15 est déjà marqué comme non premier ; on ajoutera donc plutôt \((5, 25)\).
  • Lors du premier ajout d’un nombre premier \(p\) à la liste prochains, le multiple associé est \(p^2\). En effet, tous les multiples plus petits sont ou seront traités par des nombres premiers déjà découverts.

Exemple d’exécution

  1. Initialisation

    • (ligne 4) 2 est un nombre premier et signalé comme tel. Nous ne traiterons plus des nombres impairs.
    • (ligne 5) 3 est un nombre premier.
    • (ligne 6) La liste prochains est initialisée à [(3, 9)], le multiple suivant, non pair, de 3, étant 9.
    • (ligne 7) nombre est initialisé à 5.
  2. Premier passage dans la boucle

    • (lignes 10 à 13) Le prochain multiple est 9, donc tous les nombres (impairs) de 5 (inclus) à 9 (exclu) sont premiers.
    • (ligne 12) Pour chacun de ces nouveaux nombres premiers \(p\) (5 et 7), on ajoute \((p, p^2)\) à la liste suivants.
    • La liste prochains est désormais égale à [(5, 25), (7, 49)].
    • (ligne 15) Le multiple suivant de 3 est 15 (en ignorant 12, pair). On l’ajoute à la liste.
    • La liste prochains vaut désormais [(3, 15), (5, 25), (7, 49)], et nombre vaut 11.
  3. Second passage dans la boucle

    • (lignes 10 à 13) Dans la boucle interne, les nombres premiers suivants sont découverts : 11 et 13.
    • À la fin de la boucle, on a : nombre = 17 et prochains = [(3, 21), (5, 25), (7, 49), (11, 121), (13, 169)].
  4. Passages suivants

    • Troisième : Les nombres premiers 17 et 19 sont découverts ; nombre = 23 et prochains = [(5, 25), (3, 27), (7, 49), (11, 121), (13, 169), (17, 289), (19, 361)].
    • Quatrième : Le nombre premier 23 est découvert ; nombre = 27 et prochains = [(3, 27), (5, 35), (7, 49), (11, 121), (13, 169), (17, 289), (19, 361), (23, 529)].
    • Cinquième : Aucun nouveau nombre premier ; nombre = 29 et prochains = [(3, 33), (5, 35), (7, 49), (11, 121), (13, 169), (17, 289), (19, 361), (23, 529)].
    • Etc.

Performances

Sur un ordinateur de bureau, j’ai été capable de générer le premier million des nombres premiers en moins d’une heure (52 minutes). Par peur du ridicule, je n’ose pas comparer cela aux performances des algorithmes qui battent des records, mais je suis quand même content de moi… 🤓🙂