En tête general

(C) Copyright Franck CHEVRIER 2019-2020 http://www.python-lycee.com/

Pour exécuter une saisie Python, sélectionner la cellule et valider avec SHIFT+Entrée.

Crible d'Eratosthène (corrigé)

1. Description de la méthode et mise en œuvre

On dispose ci-dessous d’une grille donnant les 101 premiers nombres entiers.

Grille

Le but est de barrer tous les nombres de la grille qui ne sont pas premiers. On considère l’algorithme ci-dessous.

► On dispose de la liste des nombres entiers de 0 à 100.

► Barrer 0 et 1.

► Parcourir dans l’ordre tous les entiers k de 2 à 100. Si le nombre k n’est pas barré :

  • Entourer k
  • Barrer tous les multiples stricts de k dans la liste

► Renvoyer la liste des nombres qui ont été entourés.

1.1. Suivre la vidéo ci-dessous pour appliquer le crible d'Eratosthène.

1.2. Justifier brièvement pourquoi, après exécution de l’algorithme :

  • les nombres barrés ne sont pas premiers ;
  • les nombres entourés sont premiers.

Cette méthode de détermination des premiers nombres premiers est appelée Crible d’Eratosthène.

2. Implémentation en langage Python

2.1. Ecrire une instruction Python qui génère une liste Python $L$ de longueur $101$ telle que $L[k]=k$, c'est-à-dire $L=[0,1,2,3,…,100]$.

In [1]:
L=[k for k in range(101)]

Le but est de remplacer tous les nombres non premiers d’une telle liste par des $0$ à l’aide du crible d’Eratosthene. ($0$ correspondra ainsi à un nombre barré de la grille vue dans la partie I)

2.2. Tester le script Python ci-dessous pour différentes valeurs entières non nulles de $k$. Que permet-il d'obtenir?

In [2]:
k=13 # Modifier cette valeur pour les tests

for j in range(2*k,101,k):
    print(j)
26
39
52
65
78
91

2.3. A l’aide des questions précédentes, écrire une fonction Python Crible_Eratosthene qui applique l’algorithme de la partie I.

La fonction renverra la liste $L=[0,0,2,3,0,…,0]$, telle que $L[k] = \begin{Bmatrix} 0 & \hbox{ si $k$ n'est pas premier } \\ k & \hbox{ si $k$ est premier} \end{Bmatrix} $

In [3]:
def Crible_Eratosthene():
    L=[k for k in range(101)]           # on génère la liste telle que L[k]=k
    L[1]=0                              # on "barre" 1 (et 0 est déjà "barré")
    for k in range(2,101):              # pour tous les k de 2 à 100
        if L[k]!=0:                     # si k n'est pas "barré":
            for j in range(2*k,101,k):  # on "barre" tous les multiples stricts de k
                L[j]=0
    return L                            # on renvoie la liste obtenue

Crible_Eratosthene()
Out[3]:
[0,
 0,
 2,
 3,
 0,
 5,
 0,
 7,
 0,
 0,
 0,
 11,
 0,
 13,
 0,
 0,
 0,
 17,
 0,
 19,
 0,
 0,
 0,
 23,
 0,
 0,
 0,
 0,
 0,
 29,
 0,
 31,
 0,
 0,
 0,
 0,
 0,
 37,
 0,
 0,
 0,
 41,
 0,
 43,
 0,
 0,
 0,
 47,
 0,
 0,
 0,
 0,
 0,
 53,
 0,
 0,
 0,
 0,
 0,
 59,
 0,
 61,
 0,
 0,
 0,
 0,
 0,
 67,
 0,
 0,
 0,
 71,
 0,
 73,
 0,
 0,
 0,
 0,
 0,
 79,
 0,
 0,
 0,
 83,
 0,
 0,
 0,
 0,
 0,
 89,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 97,
 0,
 0,
 0]

Modifier la fonction Crible_Eratosthene pour qu’elle renvoie la liste des nombres premiers $[2,3,5,…,97]$.

In [4]:
# fonction modifiée

def Crible_Eratosthene():
    L=[k for k in range(101)]           # on génère la liste telle que L[k]=k
    L[1]=0                              # on "barre" 1 (et 0 est déjà "barré")
    for k in range(2,101):              # pour tous les k de 2 à 100
        if L[k]!=0:                     # si k n'est pas "barré":
            for j in range(2*k,101,k):  # on "barre" tous les multiples stricts de k
                L[j]=0
    return [elt for elt in L if elt!=0] #on ne renvoie que les valeurs non nulles de L

Crible_Eratosthene()
Out[4]:
[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]

Modifier la fonction Crible_Eratosthene pour qu’elle reçoive en argument un entier $N$ et renvoie la liste de tous les nombres premiers inférieurs à $N$.

In [5]:
# fonction modifiée

def Crible_Eratosthene(N):
    L=[k for k in range(N+1)]           # on génère la liste telle que L[k]=k
    L[1]=0                              # on "barre" 1 (et 0 est déjà "barré")
    for k in range(2,N+1):              # pour tous les k de 2 à 100
        if L[k]!=0:                     # si k n'est pas "barré":
            for j in range(2*k,N+1,k):  # on "barre" tous les multiples stricts de k
                L[j]=0
    return [elt for elt in L if elt!=0] #on ne renvoie que les valeurs non nulles de L

Crible_Eratosthene(200)
Out[5]:
[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,
 101,
 103,
 107,
 109,
 113,
 127,
 131,
 137,
 139,
 149,
 151,
 157,
 163,
 167,
 173,
 179,
 181,
 191,
 193,
 197,
 199]

2.4. Calculer la fréquence des nombres premiers parmi les nombres inférieurs à $N$ pour $N=100$, $N=10000$ puis $N=1000000.$

Dans chaque cas, comparer cette fréquence avec $\frac{1}{ln(N)}$, où $ln$ est la fonction logarithme népérien.

In [6]:
# écriture d'une fonction qui renvoie les deux valeurs à comparer

from math import log

def comparaison(N):
    return len(Crible_Eratosthene(N))/N , 1/log(N)

# appel de la fonction pour N qui vaut 100, 10000 et  1000000

comparaison(100) , comparaison(10000) , comparaison(1000000) 
Out[6]:
((0.25, 0.21714724095162588),
 (0.1229, 0.10857362047581294),
 (0.078498, 0.07238241365054197))

Remarque : Il a été prouvé que, pour de grandes valeurs de $N$, la fréquence d’apparitions des nombres premiers entre $1$ et $N$, est proche de $\frac{1}{ln(N)}$ où $ln$ est la fonction logarithme népérien (Théorème des nombres premiers). Cette fréquence étant décroissante, on dit qu’il y a raréfaction des nombres premiers.

3. Optimisation de l'algorithme

3.1. Justifier que, dans l'algorithme du crible d'Eratosthène, lorsque $k$ dépasse la valeur $\sqrt{n}$ , ses multiples stricts ont forcément déjà été barrés. En déduire une fonction Crible_Eratosthene_opt où ces valeurs de $k$ ne sont plus testées.

Aide: L'instruction from math import* permet d'utiliser les fonctions sqrt (racine carrée) et floor (partie entière).

In [7]:
from math import*

def Crible_Eratosthene_opt(N):
    L=[k for k in range(N+1)]
    L[1]=0
    for k in range(2,floor(sqrt(N))+1): #on arrête la boucle dès qu'on a atteint ou dépassé sqrt(N)
        if L[k]!=0:
            for j in range(2*k,N+1,k):
                L[j]=0
    return [elt for elt in L if elt!=0]

3.2. La fonction temps_exec ci-dessous permet d'évaluer le temps d'exécution (en seconde) d'une fonction crible implémentant le crible d'Eratosthène pour la recherche des nombres premiers inférieurs à N.

Tester les appels à cette fonction pour la fonction du Crible d'Eratosthène obtenu dans la partie 2 et celle de la partie 3 pour $N=1000000$. Comparer les résultats.

In [8]:
from time import*

def temps_exec(crible,N):
    """
    Evaluation du temps d'exécution (en s) d'une fonction de crible
    pour déterminer les nombres premiers inférieurs à N
    """
    t=time()   # on récupère l'heure courante
    crible(N)  # on appelle la fonction de calcul du crible
    t=time()-t # on calcule le temps écoulé (différence entre l'heure actuelle et l'heure de départ)
    return t
In [9]:
#Test pour la fonction Crible_Eratosthene (partie 2)
temps_exec(Crible_Eratosthene,1000000)
Out[9]:
0.7603590488433838
In [10]:
#Test pour la fonction Crible_Eratosthene_opt (partie 3)
temps_exec(Crible_Eratosthene_opt,1000000)
Out[10]:
0.6206188201904297

(C) Copyright Franck CHEVRIER 2019-2020 http://www.python-lycee.com/