Le crible d’Ératosthène

Il est possible de trouver tous les nombres premiers inférieurs à n beaucoup plus rapidement qu’en testant la primalité de chaque nombre entre 2 et n. Au lieu de vérifier chaque nombre, on peut adopter une approche consistant à supprimer de manière proactive tous les nombres dont on sait qu’ils ne seront pas premiers.

Au départ, on peut marquer tous les nombres de 2 à n comme « potentiellement premiers ». Puis on supprime tous les multiples de 2 de cette liste et on marque 2 comme « définitivement premier ». Ensuite, on supprime tous les multiples de 3 et on marque 3 comme « définitivement premier ». On saute ensuite 4, car il a déjà été retiré de la liste des nombres potentiellement premiers lorsque nous avons traité 2. Le prochain nombre à considérer est 5, et on en supprime tous les multiples. On saute 6, puisque nous l’avions déjà marqué comme non premier lors du traitement de 2. On peut continuer ce processus jusqu’à atteindre n.

Simulation du crible d’Ératosthène. Cliquez sur les nombres et tentez d’activer tous les nombres premiers, tout en désactivant les autres.

Propriétés intéressantes et optimisations de l’algorithme

Une conséquence importante du fait de supprimer tous les multiples d’un nombre premier p de la liste des « potentiellement premiers », en partant du plus petit (2) puis en augmentant progressivement p, est que, au lieu de traiter tous les multiples 2·p, 3·p, 4·p, 5·p, … on peut commencer directement à p·p. En effet, tous les multiples de p comme 2·p, 3·p, 4·p, 5·p ont déjà été retirés de la liste lors du traitement des nombres 2, 3, 5, etc. Le premier nombre qui n’a pas encore été éliminé est donc le p·p.

Ainsi, lorsque nous commençons à traiter p=3, nous pouvons directement partir de 9, puisque 6 a déjà été retiré lors du traitement du nombre 2. De la même manière, pour p=5, nous pouvons directement partir de 25, puisque 10 (10 = 2·5) a été retiré lors du traitement de 2, 15 (15 = 3·5) lors du traitement de 3, et 20 (20 = 4·5) lors du traitement de 2.

prime = [True] * n                    # prime[i] = True => i est un nombre premier
prime[0] = prime[1] = False           # 0 et 1 ne sont pas premiers

for i in range(2, n):                 # Boucle de 2 à n
    if prime[i]:                      # si i est premier => marquer tous les multiples de i comme non premiers
        for j in range(i * i, n, i):  # on commence à i * i car tous les multiples plus petits ont déjà été marqués auparavant
            prime[j] = False

Sieve of Eratosthenes to find all the prime numbers smaller than n.

Simulons ce processus pour n=100 :

prime = [False, False, True, True, ..., True] de taille 100

i = 2 ⇒ prime[2] = True ⇒ for j in 4, 6, 8, ... 100 et marquer prime[j] = False

i = 3 ⇒ prime[3] = True ⇒ for j in 9, 12, ... 100 et marquer prime[j] = False

i = 4 ⇒ prime[4] = False

i = 5 ⇒ prime[5] = True ⇒ for j in 25, 30, ... 100 et marquer prime[j] = False

i = 6 ⇒ prime[6] = False

i = 7 ⇒ prime[7] = True ⇒ for j in 49, 56, ... 100 et marquer prime[j] = False

i = 8 ⇒ prime[8] = False

i = 9 ⇒ prime[9] = False

i = 10 ⇒ prime[10] = False

i = 11 ⇒ prime[11] = True ⇒ for j in [empty] et marquer prime[j] = False

On peut s’arrêter ici, car i * i est déjà plus grand que n. À partir de maintenant, on ne marquera plus aucun nombre comme False. Il suffit donc de parcourir la liste pour afficher tous les nombres premiers inférieurs à 100.

Cette approche est nettement plus rapide et effectue opérations. C’est une amélioration considérable ! Faire opérations au lieu de fait une énorme différence. Reprenons l’exemple de l’algorithme qui devait fonctionner pendant 10 ans (3650 jours) pour un calcul effectuant n opérations, et 2 mois (61 jours) pour opérations : avec , il aurait besoin de moins de 4 jours !

Une autre optimisation mentionnée dans la simulation consiste à laisser i parcourir les valeurs de 2 jusqu’à , car la boucle interne commence à i·i. Ainsi, pour tous les nombres plus grands que la racine carrée de n, on ne marquera plus de nombres comme prime[j] = False dans la boucle interne (dont la limite supérieure est n).

Entrée

La première ligne de l’entrée contient un seul entier n (2 ≤ n ≤ ).

Sortie

Le programme doit afficher tous les nombres premiers inférieurs ou égaux à n.

Exemples

Entrée	Sortie
8	2 3 5 7
17	2 3 5 7 11 13 17
19	2 3 5 7 11 13 17 19

Propriétés intéressantes et optimisations de l’algorithme

Entrée

Sortie

Exemples

Constraints

To check your solution you need to sign in

Sign in to continue