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 Pqui 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 PLa 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")J’ai complètement refait mon code en utilisant ce qu’on appelle les cycles de nombres éligibles. Voici un lien vers la méthode utilisée:
https://connect.ed-diamond.com/GNU-Linux-Magazine/glmf-121/un-algorithme-additif-et-iteratif-pour-construire-les-nombres-premiers
Je me suis limité au cycle 8 / 30 qui suppose connus les nombres premiers 2, 3 et 5.
Si on va trop loin, le tableau des flags peut être réduit considérablement, mais le tableau des cycles grandit de façon exponentielle.
J’aurais pu aller jusqu’au cycle 48 / 210 qui suppose connus les nombres premiers 2, 3, 5 et 7, mais le gain me semblait minime.
Pour accélérer, j’ai également utilisé le bytearray pour les flags et le cycle car les nombres sont petits pour ce dernier.
Je peux aller jusqu’à un milliard en à peine plus de 12 secondes sur une machine à 4 Ghz.
# Quatrième version. from time import perf_counter n = int(input("Cherchons le nombre de nombres premiers compris entre 1 et ? ")) begin = perf_counter() cycle = [4, 2, 4, 2, 4, 6, 2, 6] # Cycle 8 / 30 qui suppose que 2, 3 et 5 sont connus. lc = len(cycle) # Longueur du cycle. li = sum(cycle) # Longueur de l'intervalle couvert par un cycle. suite = [-1] * li # Table d'accès direct pour les indices. a = 0 for i, c in enumerate(cycle): suite[a] = i a += c cycle = bytearray(cycle+cycle) # Pour éviter les débordements et un parcourt cyclique. while suite[(n-7)%li] < 0: n -= 1 # Synchroniser sur un élément du cycle. s = int(n**0.5) while suite[(s-7)%li] < 0: s -= 1 nf = (n-7)//li*lc + suite[(n-7)%li] # Indice du dernier élément dans le tableau des flags. sf = (s-7)//li*lc + suite[(s-7)%li] # Indice de la position de la racine carrée. flags = bytearray([True]*(nf+1)) f = 7 # Premier entier considéré. for p in range(sf+1): if flags[p]: ff = f*f - 7 # Carré moins lle offset. r = f*lc i = suite[(f-7)%li] # Indice de démarrage du cycle pour les carrés. for w in cycle[i:i+lc]: q = ff//li*lc + suite[ff%li] # Indice du nombre. # Effacer les multiples avec du slicing. flags[q::r] = [False] * ((nf+r - q) // r) ff += w*f f += cycle[p%lc] # Nombre suivant. print(round(perf_counter()-begin, 3), "secondes") print(f'Il y a {3+sum(flags)} nombres premiers.')