{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![En tête general](img/En_tete_general.png)\n",
    "\n",
    "\n",
    "*(C) Copyright Franck CHEVRIER 2019-2020 http://www.python-lycee.com/*\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"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# PGCD par l'algorithme d'Euclide et coefficients de Bezout (corrigé)</span> "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Algorithme d'Euclide"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On considère deux entiers naturels $a$ et $b$ non nuls, dont on cherche à déterminer le PGCD.\n",
    "\n",
    "On pose $\\color{red}{a_0=a}$ et $\\color{blue}{b_0=b}$ puis on considère la suite des divisions euclidiennes suivantes, réitérées tant que le reste $r_n$ n'est pas nul.\n",
    "\n",
    "$a_0=b_0q_0+r_0$\n",
    "\n",
    "$ \\;\\;\\;\\; \\swarrow \\;\\;\\;\\;\\;\\; \\swarrow$\n",
    "\n",
    "$a_1=b_1q_1+r_1$\n",
    "\n",
    "$ \\;\\;\\;\\; \\swarrow \\;\\;\\;\\;\\;\\; \\swarrow$\n",
    "\n",
    "$a_2=b_2q_2+r_2$\n",
    "\n",
    "...\n",
    "\n",
    "$a_{n-1}=b_{n-1}q_{n-1}+r_{n-1}$\n",
    "\n",
    "$ \\;\\;\\;\\; \\swarrow \\;\\;\\;\\;\\;\\; \\swarrow$\n",
    "\n",
    "$a_n=b_nq_n+r_n$\n",
    "\n",
    "...\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\\begin{array}{} \\color{red}{a_0} &=& \\color{blue}{b_0} q_0 & + & \\color{green}{r_0} \\\\ \\; & \\color{blue}\\swarrow & \\; & \\color{green}\\swarrow \\\\ a_1 &=& b_1 q_1 & + & r_1 \\\\ \\end{array}\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\\begin{array}{} a_0 &=& b_0 q_0 & + & r_0 \\\\ \\; & \\swarrow & \\; & \\swarrow \\\\ a_1 &=& b_1 q_1 & + & r_1 \\\\ \\end{array}\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "_1. \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "où on a :\n",
    "Pour $n>=0$ ; $q_n$ et $r_n$ sont respectivement le quotient et le reste de la division de $a_n$ par $b_n$\n",
    "Pour $n>=1$ ; $a_n=b_{n-1}$ et $b_n=r_{n-1}$\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "pour tout $n\\in\\mathbb{N^*}$, on pose $a_n=b_{n-1}$ et $b_n$ le rest\n",
    "\n",
    "\n",
    "\n",
    "Un autre exemple :\n",
    "N\n",
    "⊂\n",
    "Z\n",
    "⊂\n",
    "D\n",
    "⊂\n",
    "Q\n",
    "⊂\n",
    "R\n",
    "⊂\n",
    "C\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "On dispose ci-dessous d’une grille donnant les 101 premiers nombres entiers.\n",
    "\n",
    "![Grille](img/Crible_Eratosthene_grille.png)\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",
    "<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"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__1.1. Suivre la vidéo ci-dessous pour appliquer le crible d'Eratosthène.__\n",
    "\n",
    "<video controls src=\"video/Eratosthene.mp4\" width=\"960\" height=\"540\" />\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 <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"
   ]
  },
  {
   "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 <mark>Crible_Eratosthene</mark> 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 <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$.__"
   ]
  },
  {
   "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 <mark>Crible_Eratosthene_opt</mark> où ces valeurs de $k$ ne sont plus testées.__\n",
    "\n",
    "Aide: L'instruction <mark>from math import*</mark> 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 <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.__"
   ]
  },
  {
   "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
}