Nombres premiers

Cet exercice ainsi que sa correction est proposé par Philippe Moutou. Il enseigne au lycée Henri IV à Paris.

Exercice

Écrire une fonction premiers(n) qui détermine la liste des nombres premiers inférieurs ou égaux à un entier n donné.

Selon la méthode du crible d’Ératosthène, on peut supprimer d’une liste contenant les entiers entre 2 et n tous les multiples de 2, puis supprimer tous les multiples du nombre suivant 2 (sauf erreur, cela doit être 3), etc.

Corrigé

La méthode du crible d’Ératosthène est relativement simple à mettre en oeuvre : on parcourt la liste des nombres entiers inférieurs ou égaux à n autant de fois qu’il est possible en supprimant les multiples du premier nombre non supprimé. La liste de départ est obtenue avec list(range(2,n+1)) qui contient [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] lorsque n=12. La suppression des multiples de k=2 (k indique le premier nombre non supprimé) s’obtient en redéfinissant la liste prem, par l’instruction prem=[p for p in prem if p<=k or p%k!=0] qui opère le tri p<=k or p%k!=0 signifiant : soit p est premier (inférieur au dernier nombre non supprimé), soit p n’est pas divisible par k. On recommence l’opération après avoir choisi la nouvelle valeur de k avec k=prem[prem.index(k)+1]. On arrive ainsi à [2, 3, 5, 7, 11] après l’avoir parcourue pour k=2 et k=3.

Le prochain nombre non supprimé est k=5, mais on n’a pas besoin de supprimer ses multiples car le premier qui n’a pas déjà été supprimé est $5\times5$, un nombre supérieur à n=12. Pour cette raison, on arrête la procédure quand k atteint ou dépasse $\sqrt{n}$.

from math import *
def premiers(n):
  prem=list(range(2,n+1))
  k=2
  nRacine=sqrt(n)
  while k<nRacine:
    prem=[p for p in prem if p<=k or p%k!=0]
    k=prem[prem.index(k)+1]  # nouveau nombre premier
  return prem

Liste_premiers=premiers(100)
print("Plus grand premier =",Liste_premiers[-1])
print("Nombre de premiers =",len(Liste_premiers))
print("Liste premiers :",Liste_premiers)