Nombres premiers

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

Exercice

Écrire une fonction premiers(n) qui détermine la liste des nombres premiers inférieurs ou égaux à un entier n donné.

Selon la méthode du crible d’Ératosthè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 être 3), etc.

Corrigé

La méthode du crible d’Ératosthène est relativement simple à mettre en oeuvre : on parcourt la liste des nombres entiers inférieurs ou égaux à n autant de fois qu’il est possible en supprimant les multiples du premier nombre non supprimé. La liste de dé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 supprimé) s’obtient en redéfinissant la liste prem, par l’instruction prem=[p for p in prem if p<=k or p%k!=0] qui opère le tri p<=k or p%k!=0 signifiant : soit p est premier (inférieur au dernier nombre non supprimé), soit p n’est pas divisible par k. On recommence l’opération après avoir choisi la nouvelle valeur de k avec k=prem[prem.index(k)+1]. On arrive ainsi à [2, 3, 5, 7, 11] après l’avoir parcourue pour k=2 et k=3.

Le prochain nombre non supprimé est k=5, mais on n’a pas besoin de supprimer ses multiples car le premier qui n’a pas déjà été supprimé est $5\times5$ , un nombre supérieur à n=12. Pour cette raison, on arrête la procédure quand k atteint ou dé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)

Il y a sans doute de nombreuses autres façons de générer cette liste. Nous en resterons à celle-là qui est assez concise et efficace. Sur la calculatrice, la plus grande partie de la liste est cachée à l’affichage. Il est possible de la faire défiler avec les flèches directionnelles. On peut aussi mieux penser l’affichage en mettant à profit les 30 caractères affichés par ligne : un nombre par ligne devrait permettre d’avoir un affichage correct (mais est-ce utile ?) jusqu’au plus grand nombre premier à 30 chiffres…