(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.
On dispose ci-dessous d’une grille donnant les 101 premiers nombres entiers.
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é :
► 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 :
Cette méthode de détermination des premiers nombres premiers est appelée Crible d’Eratosthène.
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]$.
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?
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} $
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()
[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]$.
# 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()
[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$.
# 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)
[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.
# é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)
((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.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).
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.
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
#Test pour la fonction Crible_Eratosthene (partie 2)
temps_exec(Crible_Eratosthene,1000000)
0.7603590488433838
#Test pour la fonction Crible_Eratosthene_opt (partie 3)
temps_exec(Crible_Eratosthene_opt,1000000)
0.6206188201904297
Pour aller plus loin : http://python.jpvweb.com/python/mesrecettespython/doku.php?id=liste_des_nombres_premiers
(C) Copyright Franck CHEVRIER 2019-2020 http://www.python-lycee.com/