Le Crible d'Ératosthène

Un algorithme élégant pour trouver les nombres premiers

Qu'est-ce que le Crible d'Ératosthène ?

Le Crible d'Ératosthène est une méthode ancienne et efficace pour trouver tous les nombres premiers jusqu'à une limite donnée. Il a été conçu par Ératosthène de Cyrène, un mathématicien grec du IIIe siècle avant J.-C.

Principe de l'algorithme

  1. Créer une liste de nombres entiers de 2 à n (où n est la limite supérieure).
  2. Commencer avec le premier nombre de la liste (2).
  3. Marquer comme composites tous les multiples de ce nombre jusqu'à n.
  4. Trouver le prochain nombre non marqué dans la liste et répéter l'étape 3.
  5. Continuer jusqu'à ce que le carré du nombre courant soit supérieur à n.

Démonstration interactive

Utilisez les contrôles ci-dessous pour voir le Crible d'Ératosthène en action :

Explication

L'algorithme commence par considérer tous les nombres de 2 à 100 comme potentiellement premiers. À chaque étape, il prend le plus petit nombre non marqué et élimine tous ses multiples, car ils ne peuvent pas être premiers. Les nombres restants à la fin sont tous les nombres premiers jusqu'à 100.

Note importante

L'optimisation clé du Crible d'Ératosthène est qu'il suffit de vérifier les multiples jusqu'à la racine carrée de la limite. Pourquoi ? Parce que si un nombre n est composé, il a au moins un facteur inférieur ou égal à √n.

Complexité de l'algorithme

La complexité temporelle du Crible d'Ératosthène est de O(n log log n), ce qui en fait l'un des algorithmes les plus efficaces pour trouver tous les nombres premiers jusqu'à une limite donnée.

Nombre approximatif de nombres premiers ≤ n : π(n) ≈ n / ln(n)

Implémentation en Python


def eratosthenes_sieve(n):
    primes = [True] * (n + 1)
    primes[0] = primes[1] = False
    
    for i in range(2, int(n**0.5) + 1):
        if primes[i]:
            for j in range(i*i, n+1, i):
                primes[j] = False
    
    return [i for i in range(n+1) if primes[i]]

# Exemple d'utilisation
print(eratosthenes_sieve(100))

Cette implémentation retourne une liste de tous les nombres premiers jusqu'à n inclus.

Applications du Crible d'Ératosthène