import numpy as np
import matplotlib.pyplot as plt

def cribleDErathostene(N):
    """
    N est un entier.
    Renvoie la liste des premiers plus petits que N construite 
    en utilisant l'algorithme  d'Erathostene.
    """
    L = [k for k in range(2, N + 1)]
    P = []
    while L != []:
        p = L[0]
        for k in range(1, N//p + 1):
            if k*p in L:
                L.remove(k*p)
        P.append(p)
    return P


def nombreDePremiers(N):
    """
    N est un entier.
    Renvoie la liste dont chaque element est [k, p_k], avec 
    k allant de 2 a N, et p_k etant le nombre de premiers plus
    petits que k.
    """
    P = cribleDErathostene(N)
    NP = []
    s = 0
    for k in range(2, N + 1):
        if k in P:
            s = s + 1
        NP.append([k, s])
    return NP

N = 12

print(f"La liste des nombre premiers plus petits que {N} est \
\n{cribleDErathostene(N)}\n")
NP = nombreDePremiers(N)
print("Pour tracer le graphe de la densite des nombres premiers\n", len(NP), NP)


fig = plt.figure()
ax = fig.add_subplot(111)  # aspect='equal'

N = 15000
NP = nombreDePremiers(N)
X = []
Y = []
Ylog = []
for L in NP:
    X.append(L[0])
    Ylog.append(np.log(L[0]) -1)
    Y.append(L[0]/L[1])


ax.plot(X, Y, color='b', linewidth=1, label=f"p_n/n")
ax.plot(X, Ylog, color='r', linewidth=.8, label=f"log(n)-1")               
ax.set_title(f'Densite des nombres premiers pour N = {N}')
ax.legend()
ax.grid()

plt.show()