Le crible d’Ératosthène en Python

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")