Aller au contenu

Crible d'Ératosthène⚓︎

Nombres premiers

  • \(0\) et \(1\) ne sont pas des nombres premiers, par définition.
  • Pour un entier \(n>1\), on dit que \(n\) est nombre premier s'il ne possède que deux diviseurs entiers \(1\) et \(n\).

Par exemple :

  • \(2\) est premier ; \(1×2\) est le seul produit d'entier égal à \(2\).
  • \(3\) est premier ; \(1×3\) est le seul produit d'entier égal à \(3\).
  • \(4\) n'est pas premier ; il est aussi multiple de \(2\), avec \(2×2 = 4\).
  • \(5\) est premier ; \(1×5\) est le seul produit d'entier égal à \(5\).

Propriété importante : un entier \(n>1\) est toujours multiple d'un nombre premier, parfois lui-même uniquement. C'est cette propriété que nous allons utiliser pour justifier le fonctionnement du crible d'Ératosthène.

On va marquer les multiples des nombres premiers, le plus petit entier non marqué sera donc un nombre premier.

Le crible d'Ératosthène

Un crible est une technique qui permet de répondre sur les caractéristiques d'entiers, non pas un à la fois, mais sur plusieurs à la fois. Il existe des cribles pour autre chose que les nombres premiers.

Le crible d'Ératosthène permet de déterminer les nombres premiers jusqu'à un certain nombre \(n\) fixé. La démarche avec un papier et un crayon est la suivante :

  • On écrit tous les entiers jusqu'à \(n\).
  • On raye \(0\) et \(1\) qui ne sont pas premiers.
  • On répète jusqu'à avoir traité tous les nombres :
    • Le prochain nombre non traité est un nombre premier ; on l'entoure.
    • On raye tous les autres multiples de ce nombre.

Crible d'Ératosthène

Avec Python, si l'on cherche les nombres premiers jusqu'à n :

  • On construit un tableau de \(n+1\) booléens crible, initialement tous égaux à True.
  • On modifie crible[0] et crible[1] à False ; \(0\) et \(1\) ne sont pas premiers. Pour \(1\), il faut vérifier avant que \(n>0\).
  • On parcourt ce tableau de gauche à droite. Pour chaque indice p :
    • Si crible[p] vaut True : le nombre \(p\) est premier.
      • On donne la valeur False à toutes les cellules de crible dont l'indice est un multiple de p, on commence avec 2*p, puis 3*p etc jusqu'à la fin du tableau.
    • Sinon, crible[p] vaut False : le nombre \(p\) n'est pas premier. On n'effectue aucun changement sur le tableau.

Utilisation : On peut établir ensuite la liste des nombres premiers jusqu'à \(n\) en filtrant les indices des cellules de crible valant True.

Astuce

L'expression Python range(2*p, n + 1, p) permet d'itérer sur tous les multiples de p, de 2*p inclus à n inclus.

Compléter la fonction eratosthene :

  • prenant en paramètre un entier n positif,
  • renvoyant le tableau crible de taille \(n+1\) contenant des booléens, crible[p] indique si p est premier.

Compléter la fonction premiers_jusque :

  • prenant en paramètre un entier n positif,
  • renvoyant la liste des nombres premiers jusqu'à \(n\).

Exemples

🐍 Console Python
>>> eratosthene(5)
[False, False, True, True, False, True]
>>> eratosthene(6)
[False, False, True, True, False, True, False]
>>> premiers_jusque(5)
[2, 3, 5]
>>> premiers_jusque(6)
[2, 3, 5]
>>> premiers_jusque(20)
[2, 3, 5, 7, 11, 13, 17, 19]
###
# testsbksl-nlbksl-nlassert eratosthene(5) == [False, False, True, True, False, True]bksl-nlassert eratosthene(6) == [False, False, True, True, False, True, False]bksl-nlassert premierspy-undjusque(5) == [2, 3, 5]bksl-nlassert premierspy-undjusque(6) == [2, 3, 5]bksl-nlassert premierspy-undjusque(20) == [2, 3, 5, 7, 11, 13, 17, 19]bksl-nlbksl-nlbksl-nl# autres testsbksl-nlbksl-nldef estpy-undpremier(n):bksl-nl if n < 2: return Falsebksl-nl for d in range(2, n):bksl-nl if n%d == 0: return Falsebksl-nl return Truebksl-nlbksl-nlbksl-nlfor n in range(37):bksl-nl attendu = [estpy-undpremier(p) for p in range(n + 1)]bksl-nl assert eratosthene(n) == attendu, f"Erreur avec n = {n}"bksl-nlfor n in range(100):bksl-nl attendu = [p for p in range(n + 1) if estpy-undpremier(p)]bksl-nl assert premierspy-undjusque(n) == attendu, f"Erreur avec n = {n}"bksl-nlbksl-nl 5/5

def eratosthene(n):bksl-nl crible = [True] py-str (n + 1)bksl-nl crible[0] = ...bksl-nl if n > 0:bksl-nl crible[1] = ...bksl-nl for p in range(...):bksl-nl if crible[p] == ...:bksl-nl # p est premierbksl-nl for kp in range(2py-strp, n + 1, p):bksl-nl crible[...] = ...bksl-nl return criblebksl-nlbksl-nldef premierspy-undjusque(n):bksl-nl crible = eratosthene(...)bksl-nl premiers = ...bksl-nl return premiersbksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert eratosthene(5) == [False, False, True, True, False, True]bksl-nlassert eratosthene(6) == [False, False, True, True, False, True, False]bksl-nlassert premierspy-undjusque(5) == [2, 3, 5]bksl-nlassert premierspy-undjusque(6) == [2, 3, 5]bksl-nlassert premierspy-undjusque(20) == [2, 3, 5, 7, 11, 13, 17, 19]bksl-nlbksl-nlbksl-nldef eratosthene(n):bksl-nl crible = [True] py-str (n + 1)bksl-nl crible[0] = Falsebksl-nl if n > 0:bksl-nl crible[1] = Falsebksl-nl for p in range(n + 1):bksl-nl if crible[p] == True:bksl-nl # p est premierbksl-nl for kp in range(2py-strp, n + 1, p):bksl-nl crible[kp] = Falsebksl-nl return criblebksl-nlbksl-nldef premierspy-undjusque(n):bksl-nl crible = eratosthene(n)bksl-nl premiers = [p for p in range(n + 1) if crible[p]]bksl-nl return premiersbksl-nlbksl-nl

A

Z