{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"\n",
"*(C) Copyright Franck CHEVRIER 2019-2020 http://www.python-lycee.com/*\n",
"\n",
" Pour exécuter une saisie Python, sélectionner la cellule et valider avec SHIFT+Entrée.\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Crible d'Eratosthène (corrigé) "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 1. Description de la méthode et mise en œuvre"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On dispose ci-dessous d’une grille donnant les 101 premiers nombres entiers.\n",
"\n",
"\n",
"\n",
"Le but est de barrer tous les nombres de la grille qui ne sont pas premiers. On considère l’algorithme ci-dessous.\n",
"\n",
"► On dispose de la liste des nombres entiers de 0 à 100.\n",
"\n",
"► Barrer 0 et 1.\n",
"\n",
"► Parcourir dans l’ordre tous les entiers k de 2 à 100. Si le nombre k n’est pas barré :\n",
"\n",
"\n",
"- Entourer k
\n",
"- Barrer tous les multiples stricts de k dans la liste
\n",
"
\n",
"\n",
"► Renvoyer la liste des nombres qui ont été entourés.\n",
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__1.1. Suivre la vidéo ci-dessous pour appliquer le crible d'Eratosthène.__\n",
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"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’Eratosthène.__\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 2. Implémentation en langage Python"
]
},
{
"cell_type": "markdown",
"metadata": {},
"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]$.__"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"L=[k for k in range(101)]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"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"
]
},
{
"cell_type": "markdown",
"metadata": {},
"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"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"26\n",
"39\n",
"52\n",
"65\n",
"78\n",
"91\n"
]
}
],
"source": [
"k=13 # Modifier cette valeur pour les tests\n",
"\n",
"for j in range(2*k,101,k):\n",
" print(j)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__2.3. A l’aide des questions précédentes, écrire une fonction Python Crible_Eratosthene 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"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[0,\n",
" 0,\n",
" 2,\n",
" 3,\n",
" 0,\n",
" 5,\n",
" 0,\n",
" 7,\n",
" 0,\n",
" 0,\n",
" 0,\n",
" 11,\n",
" 0,\n",
" 13,\n",
" 0,\n",
" 0,\n",
" 0,\n",
" 17,\n",
" 0,\n",
" 19,\n",
" 0,\n",
" 0,\n",
" 0,\n",
" 23,\n",
" 0,\n",
" 0,\n",
" 0,\n",
" 0,\n",
" 0,\n",
" 29,\n",
" 0,\n",
" 31,\n",
" 0,\n",
" 0,\n",
" 0,\n",
" 0,\n",
" 0,\n",
" 37,\n",
" 0,\n",
" 0,\n",
" 0,\n",
" 41,\n",
" 0,\n",
" 43,\n",
" 0,\n",
" 0,\n",
" 0,\n",
" 47,\n",
" 0,\n",
" 0,\n",
" 0,\n",
" 0,\n",
" 0,\n",
" 53,\n",
" 0,\n",
" 0,\n",
" 0,\n",
" 0,\n",
" 0,\n",
" 59,\n",
" 0,\n",
" 61,\n",
" 0,\n",
" 0,\n",
" 0,\n",
" 0,\n",
" 0,\n",
" 67,\n",
" 0,\n",
" 0,\n",
" 0,\n",
" 71,\n",
" 0,\n",
" 73,\n",
" 0,\n",
" 0,\n",
" 0,\n",
" 0,\n",
" 0,\n",
" 79,\n",
" 0,\n",
" 0,\n",
" 0,\n",
" 83,\n",
" 0,\n",
" 0,\n",
" 0,\n",
" 0,\n",
" 0,\n",
" 89,\n",
" 0,\n",
" 0,\n",
" 0,\n",
" 0,\n",
" 0,\n",
" 0,\n",
" 0,\n",
" 97,\n",
" 0,\n",
" 0,\n",
" 0]"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"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",
"\n",
"Crible_Eratosthene()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__Modifier la fonction Crible_Eratosthene pour qu’elle renvoie la liste des nombres premiers $[2,3,5,…,97]$.__"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[2,\n",
" 3,\n",
" 5,\n",
" 7,\n",
" 11,\n",
" 13,\n",
" 17,\n",
" 19,\n",
" 23,\n",
" 29,\n",
" 31,\n",
" 37,\n",
" 41,\n",
" 43,\n",
" 47,\n",
" 53,\n",
" 59,\n",
" 61,\n",
" 67,\n",
" 71,\n",
" 73,\n",
" 79,\n",
" 83,\n",
" 89,\n",
" 97]"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# fonction modifiée\n",
"\n",
"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 [elt for elt in L if elt!=0] #on ne renvoie que les valeurs non nulles de L\n",
"\n",
"Crible_Eratosthene()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__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$.__"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[2,\n",
" 3,\n",
" 5,\n",
" 7,\n",
" 11,\n",
" 13,\n",
" 17,\n",
" 19,\n",
" 23,\n",
" 29,\n",
" 31,\n",
" 37,\n",
" 41,\n",
" 43,\n",
" 47,\n",
" 53,\n",
" 59,\n",
" 61,\n",
" 67,\n",
" 71,\n",
" 73,\n",
" 79,\n",
" 83,\n",
" 89,\n",
" 97,\n",
" 101,\n",
" 103,\n",
" 107,\n",
" 109,\n",
" 113,\n",
" 127,\n",
" 131,\n",
" 137,\n",
" 139,\n",
" 149,\n",
" 151,\n",
" 157,\n",
" 163,\n",
" 167,\n",
" 173,\n",
" 179,\n",
" 181,\n",
" 191,\n",
" 193,\n",
" 197,\n",
" 199]"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# fonction modifiée\n",
"\n",
"def 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",
"\n",
"Crible_Eratosthene(200)\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"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"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"((0.25, 0.21714724095162588),\n",
" (0.1229, 0.10857362047581294),\n",
" (0.078498, 0.07238241365054197))"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# écriture d'une fonction qui renvoie les deux valeurs à comparer\n",
"\n",
"from math import log\n",
"\n",
"def 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",
"\n",
"comparaison(100) , comparaison(10000) , comparaison(1000000) \n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"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"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 3. Optimisation de l'algorithme"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__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.__\n",
"\n",
"Aide: L'instruction from math import* permet d'utiliser les fonctions sqrt (racine carrée) et floor (partie entière)."
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [],
"source": [
"from math import*\n",
"\n",
"def 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]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__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.__\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.__"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [],
"source": [
"from time import*\n",
"\n",
"def 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"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0.7603590488433838"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"#Test pour la fonction Crible_Eratosthene (partie 2)\n",
"temps_exec(Crible_Eratosthene,1000000)"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0.6206188201904297"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"#Test pour la fonction Crible_Eratosthene_opt (partie 3)\n",
"temps_exec(Crible_Eratosthene_opt,1000000)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Pour aller plus loin : http://python.jpvweb.com/python/mesrecettespython/doku.php?id=liste_des_nombres_premiers"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"*(C) Copyright Franck CHEVRIER 2019-2020 http://www.python-lycee.com/*\n"
]
}
],
"metadata": {
"celltoolbar": "Raw Cell Format",
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.6.4"
}
},
"nbformat": 4,
"nbformat_minor": 2
}