TP 5: Nombres premiers
Algorithme "naïf"
- Ecrire en python une fonction estPremier(n) qui retourne vrai si n est premier et faux sinon (On testera la divisibilité de n par tous les entiers k tel que $k*k \leqslant n$
- Utiliser cet algorithme pour vérifier que $P(n) = n^2 - n +41$ engendre des nombres premiers pour $n$ de -39 à 40
- Etude expérimentale de la complexité de la fonction ci-dessus
Crible d'Erathostène
Copier et exécuter le code suivant:
def cribleErathostene(n):
liste = list(range(2,n+1))
i = 0
#on prend le premier élément de la liste
tete = liste[i]
while tete*tete <= n:
k = 2
multiple = k*tete
#on enlève de la liste les multiples de tete
while multiple <= n:
if multiple in liste:
liste.remove(multiple)
k = k + 1
multiple = k*tete
#on avance d'un rang dans la liste
i = i + 1
tete = liste[i]
return liste
- On note $\pi(n)$ le nombre de nombres premiers inférieurs ou égaux à $n$. A l'aide de la fonction cribleErathostene(n) donner les valeurs de $\pi(n)$ pour $n = 100, \ 1000,\ 10\ 000$
- On admettra de plus que $\pi(100000) = 9592$ puis $\pi(10^6) = 78498$ et $\pi(10^9) = 50 847 534$. Comparer $\dfrac{n}{\pi(n)}$ à $\ln(n)$
Spirale d'Ulam
Il s'agit de construire une matrice carrée de nombres entiers d'ordre impair contenant une spirale d'entiers
Copier et compléter le code suivant:
def ulam(n):
''' n est impair'''
mat = np.zeros((n,n))
#En partant du centre de la matrice
#construire une spirale 1,2,...n
return mat
Parcourir la matrice et en utilisant le crible d'Eratosthene remplacer chaque entier par 0 si le nombre est premier 1 sinon
Puis afficher l'image