(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]$.
# Effectuer la saisie nécessaire
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=7 # Modifier cette valeur pour les tests
for j in range(2*k,101,k):
print(j)
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} $
# Ecrire la fonction
Modifier la fonction Crible_Eratosthene pour qu’elle renvoie la liste des nombres premiers $[2,3,5,…,97]$.
# Modifier la fonction et tester ici
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$.
# Modifier la fonction et tester ici
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.
# Effectuer les saisies nécessaires
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).
#Ecrire la fonction Crible_Eratosthene_opt
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)
#Test pour la fonction Crible_Eratosthene_opt (partie 3)
temps_exec(Crible_Eratosthene_opt,1000000)
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/