{
 "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": [
    "# Crible d'Eratosthène"
   ]
  },
  {
   "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",
    "![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\" />"
   ]
  },
  {
   "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": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Effectuer la saisie nécessaire\n"
   ]
  },
  {
   "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": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "k=7 # 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": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Ecrire la fonction\n"
   ]
  },
  {
   "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": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Modifier la fonction et tester ici\n"
   ]
  },
  {
   "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": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Modifier la fonction et tester ici\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": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Effectuer les saisies nécessaires\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": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Ecrire la fonction Crible_Eratosthene_opt\n"
   ]
  },
  {
   "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.__\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "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\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Test pour la fonction Crible_Eratosthene (partie 2)\n",
    "temps_exec(Crible_Eratosthene,1000000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "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/*"
   ]
  }
 ],
 "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
}