Le crible d’Ératosthène en Python

crible ératosthène Python

Le crible d’Ératosthène en Python

Le crible d’Ératosthène en Python n’est pas très long à implémenter. Il existe sans doute plusieurs façons de voir les choses; je vais vous en présenter une.

crible ératosthène Python
Ératosthène (image de Wikipedia)

Le crible d’Ératosthène en Python: la logique

Rappelons avant tout que le crible d’Ératosthène consiste à prendre la liste de tous les entiers de 2 à un certain entier naturel n, puis à supprimer tous les multiples des nombres rencontrés.

On commence donc à retenir “2” et à supprimer tous les nombres pairs (multiples de 2).

Ensuite, on prend le premier entier qui suit “2” et qui n’a pas été supprimé: c’est “3”. On supprime alors de la liste les multiples de 3 qui suivent.

L’entier suivant est “5”; on le retient et on supprime tous les multiples de 5 qui restent.

Etc.

Le crible d’Ératosthène en Python: le programme

L’idée consiste donc à prendre la liste de tous les entiers de 2 à n, de la parcourir en supprimant tous les multiples des nombres rencontrés. Facile non ? Ben… ça dépend !

Mon idée est de construire une liste L = [ 2 , 3 , … , n ] et d’initialiser une liste P vide pour y mettre tous les nombres rencontrés qui ne seront pas barrés.

Une première version

C’est la première version qui m’est venue en tête:

# Crible d’Ératosthène - version 1

def eratosthene(n):
    L = [ i for i in range(2,n+1) ]
    P = [ ]
    for i in L:
        if len(P) == 0:
            P.append(i)
        else:
            prem = True
            for k in P:
                if i % k == 0:
                    prem = False
            if prem == True:
                P.append(i)
    
    return P

qui donne par exemple:

>>> eratosthene(100)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Une deuxième version

À bien y réfléchir, la première version n’était pas exactement ce que je voulais faire. J’ai donc écrit une autre version:

# Crible d’Ératosthène - version 2

def eratosthene(n):
    L = [ i for i in range(2,n+1) ]
    P = [ ]
    
    while len(L) != 0:
        P.append(L[0])
        i = L[0]
        for k in L:
            if k % i == 0:
                del(L[L.index(k)])
    
    return P

La logique de cette version colle plus à ce que je voulais faire, à savoir parcourir la liste L et, pour chaque élément rencontré, le mettre dans la liste P et supprimer tous ses multiples. La logique est précisément:

  • Tant que L est non vide, j’ajoute à P le premier élément de L;
  • je parcours L et supprime tous les multiples de l’élément qui vient d’être ajouté à P.

Et c’est tout !

J’ajouterai peut-être d’autres méthodes quand j’aurai le temps… mais entretemps, vous pouvez aussi proposer votre version en commentaire (et je l’ajouterai à l’article si elle ne ressemble pas déjà à celles déjà proposées).

Stéphane Pasquet
Stéphane Pasquet

Laissez votre message