Objectif

Génération d'une liste de nombres premiers selon la méthode du crible d'Ératosthène.

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 nn 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 à nn 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=12n=12. La suppression des multiples de k=2k=2 (kk 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 pp est premier (inférieur au dernier nombre non supprimé), soit pp n'est pas divisible par kk.

On recommence l'opération après avoir choisi la nouvelle valeur de kk avec k=prem[prem.index(k)+1]. On arrive ainsi à [2, 3, 5, 7, 11] après l'avoir parcourue pour k=2k=2 et k=3k=3.

Le prochain nombre non supprimé est k=5k=5, mais on n'a pas besoin de supprimer ses multiples car le premier qui n'a pas déjà été supprimé est 5×55\times5, un nombre supérieur à n=12n=12. Pour cette raison, on arrête la procédure quand kk atteint ou dépasse n\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 façons de générer cette liste. Nous en resterons à celle-là qui est assez concise et efficace. Sur la calculatrice, la plus grande partie de la liste est cachée à l'affichage. Il est possible de la faire défiler avec les flèches directionnelles. On peut aussi mieux penser l'affichage en mettant à profit les 30 caractères affichés par ligne : un nombre par ligne devrait permettre d'avoir un affichage correct (mais est-ce utile ?) jusqu'au plus grand nombre premier à 30 chiffres…

Exécution du script.