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.
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