Crible d'Erathostène

I) Présentation

1) Objectif

L'objectif est de calculer la liste des nombres premiers plus petits qu'un entier n donné.

Nous allons exploiter et comparer deux méthodes très différentes:
    A) La méthode naïve.
    B) Le crible d'Eratosthène.

2) Principe

A) Méthode naïve

On teste successivement si 2, 3,..., n sont des nombres premiers et si oui, on les ajoute à la liste réponse.
Pour tester si un entier p 2 est premier, on teste l'existence d'un diviseur d de p vérifiant d { 2 , ... , [ p ] } .

B) Crible d'Eratosthène

  Pour calculer la liste des nombres premiers plus petits que n , il s'agit de supprimer de la liste des entiers de 2 à n tous les multiples “stricts” d'un autre entier.
En supprimant tous les multiples, à la fin il ne restera que les entiers qui ne sont multiples d'aucun entier, c'est à dire les nombres premiers.
    1) On commence par éliminer les multiples de 2
    2) Puis on élimine les multiples de 3, le plus petit entier suivant restant.
    3) Puis... puis  on élimine les multiples du plus petit entier p suivant restant. ( p est nécessairement premier car il n'est multiple d'aucun entier plus petit que lui)
     4) On peut s'arrêter lorsque p 2 > n , car un entier m n non premier aura un diviseur d n .
     5) A la fin du processus, tous les entiers qui n'ont pas été éliminés sont les nombres premiers inférieurs à n.  

3) Exemple d'exécution du crible    

Avec n = 20:
    s = [2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]
    On élimine les multiples (stricts) de p = 2: s→ [2,3,5,7,9,11,13,15,17,19]
    Le suivant est p = 3: on élimine les multiples de p :  s→ [2,3,5,7,11,13,17,19]
    Le suivant est p = 5. Mais 5 2 > 20 . C'est fini, s = [2,3,5,7,11,13,17,19] est la liste des nombres premiers plus petits que 20.

4)  Critique de l'algorithme précédent et conception d'un algorithme efficace

a) Critique

    1) Les modifications incessantes de la liste s (en éliminant les multiples stricts)  coûtent cher. Prenons un exemple:
  Si s = [2,3,4,5,6,7,8,9,10], et qu'on veut éliminer 4 de la liste s (s →[2,3,5,6,7,8,9,10]) , il faudra décaler dans s les termes 5,6,7,8,9 et 10. Et donc celà coûtera 6 opérations élémentaires.
  Une alternative simple est de "mettre à zéro" le terme à éliminer. Par exemple: si s = [2,3,4,5,6,7,8,9,10], et qu'on veut éliminer 4 de la liste s, alors s → [2,3,0,5,6,7,8,9,10]. Et donc celà coûtera une seule opération élémentaire.
A la fin de l'algorithme du crible, les nombres premiers seront les nombres non nuls de s.

    2) D'autre part, pour tester si un terme s[i] de s est divisible par p et l'éliminer , il faut tester si le reste de la division de s[i] par p est nul puis affecter 0 à s[i].  Mais si au départ, on a pris soin d'initialiser s à [0,1,2,...,n] (et donc on a s[i] = i), on saura que les multiples de p dans s se retouvent aux positions 2p, 3p,...k p avec  k p ≤ n. Et alors l'affectation s[k*p] = 0 annulera (sans test préliminaire) le bon terme de s.

b) Exemple d'exécution du crible efficace    

Avec n = 20. On part de s = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]
    On met à zéro les multiples (stricts) de p = 2: s→ [0,1,2,3,0,5,0,7,0,9,0,11,0,13,0,15,0,17,0,19,0]
    Le suivant non nul est est p = 3: on met à zéro de p=3 :  s→  [0,1,2,3,0,5,0,7,0,0,0,11,0,13,0,0,0,17,0,19,0]
    Le suivant est p = 5. Mais 5 2 > 20 . C'est fini, la liste des nombres strictement plus grands que 1 de s, soit [2,3,5,7,11,13,17,19] est la liste des nombres premiers plus petits que 20.

5) Algorithmes du crible en pseudo-code

a) Crible direct

s = [2,3,4,...,n]
p, ip = 2, 0            # ip est la position de p dans la liste s
tant que p ≤ sqrt(n):
      suprimer dans la liste s les multiples stricts de p
      ip = ip + 1        # On passe à l'entier restant suivant de la liste s
      p = s[ip]
résultat = s      

b) Crible efficace

s = [0,1,2,...,n]
pour p variant de 2 à sqrt(n):
    si s[p] ≠ 0, mettre à 0 les termes s[i*p] (avec i ≥ 2) de s
résultat = termes > 1 de s

II) Algorithmes de calcul de la liste des nombres premiers

La liste des nombres premiers plus petits que 100 est [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] .

Q1) Ecrire une fonction premier(n) (avec n entier ≥ 2) à valeurs booléennes renvoyant True si et seulement si n est premier.

On rappelle qu' un entier n ≥ 2 est premier si et seulement si il n'admet aucun diviseur d vérifiant d { 2 , ... , [ n ] } .
Ecrire cette fonction premier(n) avec une boucle while.

Q2) En utilisant la fonction premier(n), écrire une fonction liste_premiers(n) (avec n entier ≥ 2) calculant la liste des nombres premiers ≤ n.

(Tester successivement si 2, 3,..., n sont des nombres premiers et si oui, les ajouter à la liste réponse. )

Q3) Ecrire une fonction crible_direct(n) (avec n entier ≥ 2) calculant la liste des nombres premiers ≤ n, en suivant les indications données au I5a), par éliminations successives des multiples stricts.

Q4) Ecrire une fonction crible_efficace(n) (avec n entier ≥ 2) calculant la liste des nombres premiers ≤ n, en suivant les indications données au I5b), par mise à zéro des multiples stricts.

On cherche à améliorer encore l'algorithme du crible.

    (1) Plutôt que de travailler sur une liste s = [0, 1, 2,..., n] d'entiers, il est plus rapide de travailler sur une liste s = [True]*(n+1) de booléens, l'instruction s[k * p] = 0 devenant s[k * p] = False. A la fin du crible, les entiers p premiers seront les entiers pour lesquels s[p] = True

    (2) On peut remarquer que pour k < p, s[k * p] = False a déjà été exécutée pour une valeur inférieure de p. L'instruction pour k variant de 2 à n//p: s[k*p] = False devient pour k variant de p à n // p: s[k*p] = False.

    (3 Python a été optimisé pour travailler avec les tranches (les “slices”) dans la manipulation des listes (voir le document sur les listes).  Plutôt que d'exécuter:

for k in range(p, (n //p) + 1 ):
    s[k*p] = False

Il est plus rapide d'exécuter:

s[p*p::p] = [False]*(n//p - p + 1)

Q5) Ecrire une fonction crible_ameliore(n) (avec n entier ≥ 2) calculant la liste des nombres premiers ≤ n, en suivant les indications précédentes.

III) Comparaison de l'efficacité des divers algorithmes

La fonction comparaison_algorithmes(liste_test) suivante calcule, pour chacun des quatre algorithmes, les durées d'exécutions (sans l'affichage du résultat) pour des valeurs de n dans liste_test.

import time
def comparaison_algorithmes(plage):
    """ Calculs des durées pour n dans plage"""
    algos = (liste_premiers, crible_direct, crible_efficace, crible_ameliore)
    for n in plage:
        print()
        print("n = {0}".format(n))
        print("*"*12)
        for algo in algos:
            t = time.perf_counter()
            algo(n)
            t = time.perf_counter() - t
            print("Durée {0} = {1:.3} s".format(str(algo.__name__),t))

Par exemple, comparaison_algorithmes([1000, 10000, 100000, 200000]) renvoie sur mon PC:

n = 1000
************
Durée liste_premiers = 0.00196 s
Durée crible_direct = 0.000951 s
Durée crible_efficace = 0.000236 s
Durée crible_ameliore = 0.000108 s

n = 10000
************
Durée liste_premiers = 0.0267 s
Durée crible_direct = 0.0259 s
Durée crible_efficace = 0.0028 s
Durée crible_ameliore = 0.00091 s

n = 100000
************
Durée liste_premiers = 0.446 s
Durée crible_direct = 1.77 s
Durée crible_efficace = 0.0317 s
Durée crible_ameliore = 0.00961 s

n = 200000
************
Durée liste_premiers = 1.1 s
Durée crible_direct = 6.94 s
Durée crible_efficace = 0.0689 s
Durée crible_ameliore = 0.0194 s

Q6) Recopier cette fonction comparaison_algorithmes(liste_test)et tester comparaison_algorithmes([1000, 10000, 100000, 200000]) sur votre PC. Les résultats peuvent être différents des valeurs ci-dessus, mais devraient être proportionnels.

IV) Evaluation expérimentale de la complexité des algorithmes

1) Méthode

  On fait comme hypothèse (critiquable) que la durée duree(n) d'exécution d'un algorithme algo(n) est proportionnelle au coût C(n) de cet algorithme, et on cherche expérimentalement  une fonction f ( n ) la plus simple possible telle qu'il existe une constante k > 0 vérifiant duree ( n ) + k f ( n ) .

  Avec l'hypothèse de proportionnalité, on en déduit alors que le coût de algo ( n ) est en O ( f ( n ) ) .

  La recherche de cette fonction f sera faite à partir de tracés de graphes de la fonction g ( n ) = duree ( n ) f ( n ) , pour n dans une plage significative: les valeurs de n doivent être “nombreuses” et “grandes”. Lorsque (graphiquement) la fonction g ( n ) semblera tendre vers une constante k > 0 lorsque n tend vers l'infini, on aura trouvé la fonction f ( n ) que l'on cherche.

Les difficultés pour mettre en œuvre ces idées sont de deux ordres:
    • tâtonner pour trouver la fonction f ( n )
    •• choisir des plages significatives de valeurs de n

  Le second point est le plus délicat: le temps de calcul doit rester raisonnable, ce qui est difficile avec des valeurs de n “nombreuses” et “grandes”...

2) Algorithmes de test

import time
import numpy as np
import pylab as plt

def duree(algo, n):
    """ durée d'exécution de algo(n)"""
    t = time.perf_counter()
    algo(n)
    return time.perf_counter() - t

def graphe(algo, f, plage):
    """ graphe de duree(algo, n) / f(n) pour n dans plage"""
    plage_y = [duree(algo, n) / f(n) for n in plage]
    plt.grid(True)
    plt.plot(plage_y)
    plt.show()

  Une plage significative de valeurs pour n pourrait être plage = [1000 * 2**n for n in range(10)] . La valeur 10 doit être adaptée, vers le haut ou vers le bas, en fonction de la vélocité du PC et surtout de l'algorithme testé.

Par exemple, sur mon PC, des valeurs de n raisonnables pour les algos (liste_premiers, crible_direct, crible_efficace, crible_ameliore) sont (10, 9, 14, 15) .

Q7) Trouver des fonctions simples f ( n ) , du type f ( n ) = n α ou bien f ( n ) = n α ln β ( n ) telles que (expérimentalement), les algorithmes (liste_premiers, crible_direct, crible_efficace, crible_ameliore) soient de complexité O ( f ( n ) ) .

V) Evaluation théorique de la complexité des algorithmes

Elles sont difficiles à évaluer avec précision. On va donc les encadrer.

1) liste_premiers(n)

  Si on note CP ( n ) le coût de la fonction premier(n), le coût C ( n ) de la fonction liste_premiers(n) est   C ( n ) = O ( Σ p = 2 n CP ( p ) )

  Or   1 CP ( n ) O ( n ) , car CP ( n ) = O ( 1 ) lorsque n est pair, par exemple, et CP(n) = O ( n ) lorsque n est premier.

Comme O ( Σ p = 2 n p ) = O ( n 3 2 )   ( assez facile à montrer), alors O ( n ) C ( n ) O ( n 3 2 ) .

2) crible_efficace

  Le coût C ( n ) est C ( n ) = Σ p = 2 n CI ( p ) , avec   CI ( p ) le cout d'une itération de la boucle “pour p”.
  Or CI ( p )   est compris entre O ( 1 ) et   O ( n p ) . Comme   O ( Σ p = 2 n n p ) = n O ( Σ p = 2 n 1 p ) = O ( n ln ( n ) )    (assez facile à montrer), alors O ( n ) C ( n ) O ( n ln ( n ) ) .

Q8) Vérifier que les fonctions f ( n ) trouvées expérimentalement au IV) sont compatibles avec les encadrements donnés ci-dessus.

© 2014 - Eric Obermeyer      Powered by      Corrigé