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

Affiche les nombres premiers.

usage: erathostene [-h] [--version]

Named Arguments

--version

show program’s version number and exit

This program prints prime numbers until it is killed.

Algorithme

Code source

 1def premiers():
 2    """Itère sur l'ensemble des nombres premiers."""
 3    yield 2
 4    prochains = {}
 5
 6    for n in itertools.count(3, 2):
 7        if n not in prochains:
 8            yield n
 9            prochains[n**2] = n
10            continue
11
12        for i in itertools.count(n, 2 * prochains[n]):
13            if i not in prochains:
14                prochains[i] = prochains[n]
15                del prochains[n]
16                break

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 construit un dictionnaire prochains dont les clefs sont des nombres pas encore rencontrés, et les valeurs des nombres premiers. Par exemple, prochains[p] == m signifie que 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 (ce qui n’a pas de sens ici, puisqu’une telle table n’existe pas), on ajoute au dictionnaire 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 est un dictionnaire vide.

  2. On considère n :

  • Si n n’est pas une clef du dictionnaire prochains, il est premier. On le renvoit (yield n), et on affecte premiers[n**2] = n, ce qui signifie que la clef n**2 est le prochain multiple du nombre premier n à étudier.

  • Sinon, n est une clef du dictionnaire. Donc il est multiple du nombre premier prochains[n]. On supprime alors prochains[n], et on crée dans le dictionnaire une nouvelle entrée prochains[m] = p, où p était la valeur de prochains[n] (c’est-à-dire un des diviseurs premiers de n), et m est le prochain multiple de p.

    En d’autres termes, dans notre crible d’Érathostène, on raye le prochain nombre multiple du nombre premier p.

  1. On ajoute 1 à n, 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).

  • 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

Par exemple, au bout de quelques tours de boucles, alors que \(n=13\), la varibles prochains vaut:

{
  15: 3,
  25: 5,
  49: 7,
  121: 11,
 }

Cela signifie que dans notre crible d’Érathostène, à partir du nombre 13 :

  • le prochain multiple de 3 est 15 ;

  • le prochain multiple de 5 est 25 ;

  • le prochain multiple de 7 est 49 ;

  • le prochain multiple de 11 est 121.

Au tour suivant, \(n=15\). Puisque 15 est une clef du dictionnaire, il n’est pas premier. On le retire, et on ajoute prochains[21] = 3 (ce qui signifie que le prochain multiple de 3 est 21) :

{
  21: 3,
  25: 5,
  49: 7,
  121: 11,
  169: 13,
}

Au tour suivant, \(n=17\), qui n’est pas une clef du dictionnaire : c’est donc un nombre premier, et on ajoute prochains[17] = 17**2 comme le prochain nombre multiple de 17 à rayer (il y a d’autres nombres multiples de 17 avant \(17^2\), mais il est inutile de les rayer ici car ils seront rayés comme multiples de nombres plus petits).

Performances

Sur mon ordinateur portable, j’ai été capable de générer les nombres premiers suivants :

  • un million de nombres premiers en 7 secondes ;

  • dix millions de nombres premiers en 1 minute et demi.

J’ai été jusqu’à calculer le 70140686ᵉ nombre premier (1403273909), en utilisant 10Go de mémoire. Après cela, le programme s’est arrêté, sans que je comprenne pourquoi…

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… 🤓🙂