#!/usr/bin/env python
# coding: utf-8

# ![En tête general](img/En_tete_general.png)
# 
# 
# *(C) Copyright Franck CHEVRIER 2019-2020 http://www.python-lycee.com/*
# 
# <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>.
# 

# # Crible d'Eratosthène <span style="color: red"> (corrigé)</span> 

# ## 1. Description de la méthode et mise en œuvre

# On dispose ci-dessous d’une grille donnant les 101 premiers nombres entiers.
# 
# ![Grille](img/Crible_Eratosthene_grille.png)
# 
# Le but est de barrer tous les nombres de la grille qui ne sont pas premiers. On considère l’algorithme ci-dessous.
# 
# <span style="color: #CB1182">► On dispose de la liste des nombres entiers de 0 à 100.</span>
# 
# <span style="color: #CB1182">► Barrer 0 et 1.</span>
# 
# <span style="color: #CB1182">► Parcourir dans l’ordre tous les entiers k de 2 à 100. Si le nombre k n’est pas barré :</span>
# 
# <ul style="color: #CB1182">
# <li>Entourer k</li> 
# <li>Barrer tous les multiples stricts de k dans la liste</li>
# </ul>
# 
# <span style="color: #CB1182">► Renvoyer la liste des nombres qui ont été entourés.</span>
# 
# 
# 

# __1.1. Suivre la vidéo ci-dessous pour appliquer le crible d'Eratosthène.__
# 
# <video controls src="video/Eratosthene.mp4" width="960" height="540" />
# 

# __1.2. Justifier brièvement pourquoi, après exécution de l’algorithme :__
# * __les nombres barrés ne sont pas premiers ;__
# * __les nombres entourés sont premiers.__
# 
# __Cette méthode de détermination des premiers nombres premiers est appelée Crible d’Eratosthène.__
# 

# ## 2. Implémentation en langage Python

# __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]$.__

# In[1]:


L=[k for k in range(101)]


# 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?__
# 

# In[2]:


k=13 # 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 <mark>Crible_Eratosthene</mark> 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}
# $__
# 

# In[3]:


def Crible_Eratosthene():
    L=[k for k in range(101)]           # on génère la liste telle que L[k]=k
    L[1]=0                              # on "barre" 1 (et 0 est déjà "barré")
    for k in range(2,101):              # pour tous les k de 2 à 100
        if L[k]!=0:                     # si k n'est pas "barré":
            for j in range(2*k,101,k):  # on "barre" tous les multiples stricts de k
                L[j]=0
    return L                            # on renvoie la liste obtenue

Crible_Eratosthene()


# __Modifier la fonction <mark>Crible_Eratosthene</mark> pour qu’elle renvoie la liste des nombres premiers $[2,3,5,…,97]$.__

# In[4]:


# fonction modifiée

def Crible_Eratosthene():
    L=[k for k in range(101)]           # on génère la liste telle que L[k]=k
    L[1]=0                              # on "barre" 1 (et 0 est déjà "barré")
    for k in range(2,101):              # pour tous les k de 2 à 100
        if L[k]!=0:                     # si k n'est pas "barré":
            for j in range(2*k,101,k):  # on "barre" tous les multiples stricts de k
                L[j]=0
    return [elt for elt in L if elt!=0] #on ne renvoie que les valeurs non nulles de L

Crible_Eratosthene()


# __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$.__

# In[5]:


# fonction modifiée

def Crible_Eratosthene(N):
    L=[k for k in range(N+1)]           # on génère la liste telle que L[k]=k
    L[1]=0                              # on "barre" 1 (et 0 est déjà "barré")
    for k in range(2,N+1):              # pour tous les k de 2 à 100
        if L[k]!=0:                     # si k n'est pas "barré":
            for j in range(2*k,N+1,k):  # on "barre" tous les multiples stricts de k
                L[j]=0
    return [elt for elt in L if elt!=0] #on ne renvoie que les valeurs non nulles de L

Crible_Eratosthene(200)


# __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.__
# 

# In[6]:


# écriture d'une fonction qui renvoie les deux valeurs à comparer

from math import log

def comparaison(N):
    return len(Crible_Eratosthene(N))/N , 1/log(N)

# appel de la fonction pour N qui vaut 100, 10000 et  1000000

comparaison(100) , comparaison(10000) , comparaison(1000000) 


# 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. Optimisation de l'algorithme

# __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.__
# 
# Aide: L'instruction <mark>from math import*</mark> permet d'utiliser les fonctions sqrt (racine carrée) et floor (partie entière).

# In[7]:


from math import*

def Crible_Eratosthene_opt(N):
    L=[k for k in range(N+1)]
    L[1]=0
    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)
        if L[k]!=0:
            for j in range(2*k,N+1,k):
                L[j]=0
    return [elt for elt in L if elt!=0]


# __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>.__
# 
# __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.__

# In[8]:


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


# In[9]:


#Test pour la fonction Crible_Eratosthene (partie 2)
temps_exec(Crible_Eratosthene,1000000)


# In[10]:


#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/*
#