{"cells":[{"metadata":{},"cell_type":"markdown","source":"![En tête general](https://raw.githubusercontent.com/PythonLycee/PyLyc/master/img/En_tete_general.png)\n\n\n<i>© Copyright Franck CHEVRIER 2019-2022 https://www.python-lycee.com.</i><br>\n<i>Les activités partagées sur <a href=\"https://capytale2.ac-paris.fr/web/accueil\"><strong>Capytale</strong></a> sont sous licence <a href=\"https://creativecommons.org/licenses/by-sa/3.0/fr/\">Creative Commons</a>.</i>\n\n<span style=\"color: #9317B4\"> Pour exécuter une saisie Python, sélectionner la cellule et valider avec </span><span style=\"color: #B317B4\"><strong>SHIFT+Entrée</strong></span>.\n"},{"metadata":{},"cell_type":"markdown","source":"# Crible d'Ératosthène <span style=\"color: red\"> (corrigé)</span> "},{"metadata":{},"cell_type":"markdown","source":"## 1. Description de la méthode et mise en œuvre"},{"metadata":{},"cell_type":"markdown","source":"On dispose ci-dessous d’une grille donnant les 101 premiers nombres entiers.\n\n![Grille](https://raw.githubusercontent.com/PythonLycee/PyLyc/master/img/Crible_Eratosthene_grille.png)\n\nLe but est de barrer tous les nombres de la grille qui ne sont pas premiers. On considère l’algorithme ci-dessous.\n\n<span style=\"color: #CB1182\">► On dispose de la liste des nombres entiers de 0 à 100.</span>\n\n<span style=\"color: #CB1182\">► Barrer 0 et 1.</span>\n\n<span style=\"color: #CB1182\">► Parcourir dans l’ordre tous les entiers k de 2 à 100. Si le nombre k n’est pas barré :</span>\n\n<ul style=\"color: #CB1182\">\n<li>Entourer k</li> \n<li>Barrer tous les multiples stricts de k dans la liste</li>\n</ul>\n\n<span style=\"color: #CB1182\">► Renvoyer la liste des nombres qui ont été entourés.</span>\n\n\n"},{"metadata":{},"cell_type":"markdown","source":"__1.1. Suivre la vidéo ci-dessous pour appliquer le crible d'Ératosthène.__\n\n<video controls src=\"https://raw.githubusercontent.com/PythonLycee/PyLyc/master/video/Eratosthene.mp4\" width=\"960\" height=\"540\" />"},{"metadata":{},"cell_type":"markdown","source":"__1.2. Justifier brièvement pourquoi, après exécution de l’algorithme :__\n* __les nombres barrés ne sont pas premiers ;__\n* __les nombres entourés sont premiers.__\n\n__Cette méthode de détermination des premiers nombres premiers est appelée Crible d’Ératosthène.__\n"},{"metadata":{},"cell_type":"markdown","source":"## 2. Implémentation en langage Python"},{"metadata":{},"cell_type":"markdown","source":"__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]$.__"},{"metadata":{"trusted":false},"cell_type":"code","source":"L=[k for k in range(101)]","execution_count":1,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"Le but est de remplacer tous les nombres non premiers d’une telle liste par des $0$ à l’aide du crible d’Eratosthene.\n($0$ correspondra ainsi à un nombre barré de la grille vue dans la partie I)\n"},{"metadata":{},"cell_type":"markdown","source":"__2.2. Tester le script Python ci-dessous pour différentes valeurs entières non nulles de $k$. Que permet-il d'obtenir?__\n"},{"metadata":{"trusted":false},"cell_type":"code","source":"k=13 # Modifier cette valeur pour les tests\n\nfor j in range(2*k,101,k):\n    print(j)","execution_count":2,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"__2.3.  A l’aide des questions précédentes, écrire une fonction Python <mark>Crible_Eratosthene</mark> qui applique l’algorithme de la partie I.__\n\n__La fonction renverra la liste $L=[0,0,2,3,0,…,0]$, telle que \n$L[k] = \n\\begin{Bmatrix}\n   0 & \\hbox{ si $k$ n'est pas premier }  \\\\\n   k & \\hbox{ si $k$ est premier}  \n\\end{Bmatrix}\n$__\n"},{"metadata":{"trusted":false},"cell_type":"code","source":"def Crible_Eratosthene():\n    L=[k for k in range(101)]           # on génère la liste telle que L[k]=k\n    L[1]=0                              # on \"barre\" 1 (et 0 est déjà \"barré\")\n    for k in range(2,101):              # pour tous les k de 2 à 100\n        if L[k]!=0:                     # si k n'est pas \"barré\":\n            for j in range(2*k,101,k):  # on \"barre\" tous les multiples stricts de k\n                L[j]=0\n    return L                            # on renvoie la liste obtenue\n\nCrible_Eratosthene()","execution_count":3,"outputs":[{"data":{},"execution_count":3,"metadata":{},"output_type":"execute_result"}]},{"metadata":{},"cell_type":"markdown","source":"__Modifier la fonction <mark>Crible_Eratosthene</mark> pour qu’elle renvoie la liste des nombres premiers $[2,3,5,…,97]$.__"},{"metadata":{"trusted":false},"cell_type":"code","source":"# fonction modifiée\n\ndef Crible_Eratosthene():\n    L=[k for k in range(101)]           # on génère la liste telle que L[k]=k\n    L[1]=0                              # on \"barre\" 1 (et 0 est déjà \"barré\")\n    for k in range(2,101):              # pour tous les k de 2 à 100\n        if L[k]!=0:                     # si k n'est pas \"barré\":\n            for j in range(2*k,101,k):  # on \"barre\" tous les multiples stricts de k\n                L[j]=0\n    return [elt for elt in L if elt!=0] #on ne renvoie que les valeurs non nulles de L\n\nCrible_Eratosthene()","execution_count":4,"outputs":[{"data":{},"execution_count":4,"metadata":{},"output_type":"execute_result"}]},{"metadata":{},"cell_type":"markdown","source":"__Modifier la fonction <mark>Crible_Eratosthene</mark> pour qu’elle reçoive en argument un entier $N$ et renvoie la liste de tous les nombres premiers inférieurs à $N$.__"},{"metadata":{"trusted":false},"cell_type":"code","source":"# fonction modifiée\n\ndef Crible_Eratosthene(N):\n    L=[k for k in range(N+1)]           # on génère la liste telle que L[k]=k\n    L[1]=0                              # on \"barre\" 1 (et 0 est déjà \"barré\")\n    for k in range(2,N+1):              # pour tous les k de 2 à 100\n        if L[k]!=0:                     # si k n'est pas \"barré\":\n            for j in range(2*k,N+1,k):  # on \"barre\" tous les multiples stricts de k\n                L[j]=0\n    return [elt for elt in L if elt!=0] #on ne renvoie que les valeurs non nulles de L\n\nCrible_Eratosthene(200)\n","execution_count":5,"outputs":[{"data":{},"execution_count":5,"metadata":{},"output_type":"execute_result"}]},{"metadata":{},"cell_type":"markdown","source":"__2.4. Calculer la fréquence des nombres premiers parmi les nombres inférieurs à $N$ pour $N=100$, $N=10000$ puis $N=1000000.$__\n\n__Dans chaque cas, comparer cette fréquence avec $\\frac{1}{ln(N)}$, où $ln$ est la fonction logarithme népérien.__\n"},{"metadata":{"trusted":false},"cell_type":"code","source":"# écriture d'une fonction qui renvoie les deux valeurs à comparer\n\nfrom math import log\n\ndef comparaison(N):\n    return len(Crible_Eratosthene(N))/N , 1/log(N)\n\n# appel de la fonction pour N qui vaut 100, 10000 et  1000000\n\ncomparaison(100) , comparaison(10000) , comparaison(1000000) \n","execution_count":6,"outputs":[{"data":{},"execution_count":6,"metadata":{},"output_type":"execute_result"}]},{"metadata":{},"cell_type":"markdown","source":"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.\n"},{"metadata":{},"cell_type":"markdown","source":"## 3. Optimisation de l'algorithme"},{"metadata":{},"cell_type":"markdown","source":"__3.1. Justifier que, dans l'algorithme du crible d'Ératosthè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 <mark>Crible_Eratosthene_opt</mark> où ces valeurs de $k$ ne sont plus testées.__\n\nAide: L'instruction <mark>from math import*</mark> permet d'utiliser les fonctions sqrt (racine carrée) et floor (partie entière)."},{"metadata":{"trusted":false},"cell_type":"code","source":"from math import*\n\ndef Crible_Eratosthene_opt(N):\n    L=[k for k in range(N+1)]\n    L[1]=0\n    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)\n        if L[k]!=0:\n            for j in range(2*k,N+1,k):\n                L[j]=0\n    return [elt for elt in L if elt!=0]","execution_count":7,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"__3.2. La fonction <mark>temps_exec</mark> ci-dessous permet d'évaluer le temps d'exécution (en seconde) d'une fonction <mark>crible</mark> implémentant le crible d'Eratosthène pour la recherche des nombres premiers inférieurs à <mark>N</mark>.__\n\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.__"},{"metadata":{"trusted":false},"cell_type":"code","source":"from time import*\n\ndef temps_exec(crible,N):\n    \"\"\"\n    Evaluation du temps d'exécution (en s) d'une fonction de crible\n    pour déterminer les nombres premiers inférieurs à N\n    \"\"\"\n    t=time()   # on récupère l'heure courante\n    crible(N)  # on appelle la fonction de calcul du crible\n    t=time()-t # on calcule le temps écoulé (différence entre l'heure actuelle et l'heure de départ)\n    return t","execution_count":8,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"#Test pour la fonction Crible_Eratosthene (partie 2)\ntemps_exec(Crible_Eratosthene,1000000)","execution_count":9,"outputs":[{"data":{},"execution_count":9,"metadata":{},"output_type":"execute_result"}]},{"metadata":{"trusted":false},"cell_type":"code","source":"#Test pour la fonction Crible_Eratosthene_opt (partie 3)\ntemps_exec(Crible_Eratosthene_opt,1000000)","execution_count":10,"outputs":[{"data":{},"execution_count":10,"metadata":{},"output_type":"execute_result"}]},{"metadata":{},"cell_type":"markdown","source":"<i>© Copyright Franck CHEVRIER 2019-2022 https://www.python-lycee.com.</i><br>\n<i>Les activités partagées sur <a href=\"https://capytale2.ac-paris.fr/web/accueil\"><strong>Capytale</strong></a> sont sous licence <a href=\"https://creativecommons.org/licenses/by-sa/3.0/fr/\">Creative Commons</a>.</i>\n<br><br>\n<span style=\"font-size:8px\">Dernière modification de l'activité : Juillet 2022</span>"},{"metadata":{"trusted":true},"cell_type":"code","source":"","execution_count":null,"outputs":[]}],"metadata":{"celltoolbar":"Raw Cell Format","kernelspec":{"display_name":"Python 3","language":"python","name":"python3"}},"nbformat":4,"nbformat_minor":2}