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):
P = [ ]
for i in range(2,n+1):
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).
Pour le crible, j’ai trouvé cette méthode plus rapide dans les idées de Tristan Colombo, le rédac’chef de Linux Magazine :
def cribleÉratosthène(n): crible=[True]*(n+1) crible[0:2]=False,False m=2 while m<=(n+1)**.5: crible[2*m::m]=[False for _ in range(2*m,n+1,m)] m+=1 while not crible[m]: m+=1 return [i for i,e in enumerate(crible) if e]Bonjour,
J’ai également utilisé le principe d’un tableau de bool où je marque les multiples des nombres.
Comme le temps de parcours dépend de la longueur du tableau, j’ai cherché à en réduire la longueur.
J’utilise une boucle for car dans certaines versions, il était difficile de trouver la racine carrée du maximum.
Je commence également à effacer au carré de chaque nombre car c’est inutile de le faire avant.
Par exemple, pour 11, je commence à 121 car 33, 55, 77 ont déjà été effacés par 3, 5, 7.
Ça ne parait pas pour les petits nombres, mais c’est significatif pour les plus grands.
J’utilise aussi le slicing pour effacer car c’est beaucoup plus rapide qu’une boucle.
Dans ma premiêre version, je considère les nombres de 2 à N.
Dans la seconde version, je considère les nombres impairs de 3 à N, Je suppose 2 déjà acquis.
Dans la troisième version, je ne considère que les nombres de la forme 6*n-1 et 6*n+1. Je suppose que 2 et 3 sont déjà acquis.
J’ai laissé le code pour tester les performances.
La deuxième version est environ deux fois plus rapide que la première, et la troisième version est environ trois fois plus rapide.
Je voulais également calculer combien il y avait de nombres premiers jusqu’à ma limite.
# Première version. from time import perf_counter maximum = int(input("Entrez le nombre maximum ")) begin = perf_counter() length = maximum - 1 flags = [True] * length for indexe in range(length): if not flags[indexe]: continue number = indexe + 2 start = number * number - 2 if start >= length: break flags[start::number] = [False] * ((length - start + number - 1) // number) print(round(perf_counter()-begin, 3), "secondes") print(f"{sum(flags)} nombres premiers dans l'intervalle [1, {maximum}]") primes = [i+2 for i in range(length) if flags[i]] number = int(input("Entrez un nombre pour tester ")) test = flags[number-2] print("Le nombre", number, "est" if test else "n'est pas", "premier")# Deuxième version. from time import perf_counter maximum = int(input("Entrez le nombre maximum ")) begin = perf_counter() length = (maximum-1) // 2 flags = [True] * length for indexe in range(length): if not flags[indexe]: continue number = indexe*2 + 3 start = (number * number - 3) // 2 if start >= length: break flags[start::number] = [False] * ((length - start + number - 1) // number) print(round(perf_counter()-begin, 3), "secondes") print(f"{sum(flags)+1} nombres premiers dans l'intervalle [1, {maximum}]") primes = [2] + [2*i+3 for i in range(length) if flags[i]] number = int(input("Entrez un nombre pour tester ")) test = number==2 or number%2 and flags[(number-3)//2] print("Le nombre", number, "est" if test else "n'est pas", "premier")# Troisième version. from time import perf_counter maximum = int(input("Entrez le nombre maximum ")) begin=perf_counter() length = maximum // 3 if maximum%3 == 0 or maximum%3 == 1 and maximum%6 != 1: length -= 1 flags = [True] * length number = 1 addition = 4 toggle = 6 for indexe in range(length): number += addition addition = toggle - addition if not flags[indexe]: continue start = (number * number *2 - 5) // 6 if start >= length: break step = 2 * number flags[start::step] = [False] * ((length - start + step - 1) // step) advance = (indexe + 2) // 2 start += number - 2*advance + (indexe%2)*4*advance flags[start::step] = [False] * ((length - start + step - 1) // step) print(round(perf_counter()-begin, 3), "secondes") print(f"{sum(flags)+2} nombres premiers dans l'intervalle [1, {maximum}") primes = [2, 3] + [i//2*6+5+i%2*2 for i in range(length) if flags[i]] number = int(input("Entrez un nombre pour tester ")) test = number in [2, 3] or number%2 and number%3 and flags[(number*2-5)//6] print("Le nombre", number, "est" if test else "n'est pas", "premier")