🎛️ Regarde le crible faire son travail pas à pas
Clique « Étape suivante » pour rayer les multiples de 2, puis de 3, puis de 5, etc. Les survivants sont les nombres premiers.
Premier en cours
2
Premiers trouvés
0
Complexité totale
O(N log log N)
On cherche les premiers jusqu'à 120. On va rayer les multiples de 2, puis 3, puis 5, etc.
🪜 Ératosthène : le maître de la mesure
Ératosthène de Cyrène (276-194 av. J.-C.) est un savant grec, troisième bibliothécaire de la Bibliothèque d'Alexandrie. Il est célèbre pour avoir mesuré la circonférence de la Terre avec une erreur de seulement 2% en utilisant l'ombre d'un puits à Syène et un obélisque à Alexandrie.
Parmi ses œuvres mathématiques : un algorithme pour trouver les nombres premiers, qu'on appelle aujourd'hui le crible d'Ératosthène. Cet algorithme est si efficace qu'il est encore enseigné dans tous les cours d'algorithmique et utilisé en pratique pour les calculs cryptographiques courants.
🎯 L'algorithme : une élimination systématique
L'idée centrale : pour trouver tous les premiers ≤ N, on procède par élimination. On commence par écrire tous les entiers de 2 à N. Puis on raye systématiquement les multiples.
Algorithme du crible d'Ératosthène
- Écris tous les entiers de 2 à N.
- Le premier non rayé est 2. C'est un nombre premier. Raye tous ses multiples (4, 6, 8, ...).
- Le suivant non rayé est 3. C'est un nombre premier. Raye tous ses multiples (9, 15, 21, ...).
- Le suivant non rayé est 5. C'est un nombre premier. Raye 25, 35, ...
- Continue jusqu'à ce que le premier en cours soit > √N.
- Tous les nombres non rayés restants sont premiers.
⚡ Pourquoi on s'arrête à √N ?
Astuce essentielle : si N a un diviseur d > √N, alors N/d < √N est aussi un diviseur. Donc N a forcément un diviseur ≤ √N (s'il n'est pas premier). Ce diviseur ≤ √N est lui-même produit de premiers ≤ √N. Donc tous les multiples de premiers > √N ont déjà été rayés par les premiers ≤ √N.
Conséquence : pour cribler jusqu'à N = 100, il suffit de rayer les multiples de 2, 3, 5, 7 (les premiers ≤ √100 = 10). Pour N = 10 000, il suffit des premiers ≤ 100. Pour N = 10⁹, il suffit des premiers ≤ √10⁹ ≈ 31 623.
🚀 Complexité : O(N log log N)
Combien d'opérations effectue le crible ? On compte le nombre de fois qu'on raye un nombre. Pour chaque premier p ≤ √N, on raye N/p multiples. Le nombre total d'opérations est :
∑p premier ≤ N N/p ~ N · ln(ln N)
Cette somme est connue depuis Mertens (1874). Pour N = 10⁹, ça donne ≈ 10⁹ · ln(ln 10⁹) ≈ 3.5 milliards d'opérations. Faisable en quelques secondes sur un ordinateur moderne.
📐 Implémentation moderne (Python / C++)
Voici l'algorithme en Python :
def crible(N):
sieve = [True] * (N + 1)
sieve[0] = sieve[1] = False
for i in range(2, int(N**0.5) + 1):
if sieve[i]:
for j in range(i*i, N + 1, i):
sieve[j] = False
return [i for i, v in enumerate(sieve) if v]7 lignes. Pour N = 10⁶, ça donne tous les premiers ≤ 1 000 000 en environ 0.1 seconde. L'algorithme est si simple qu'il est souvent le premier algorithme « non trivial » qu'on apprend en cours de programmation.
🎯 Optimisations modernes
- Ignorer les pairs : on traite 2 séparément, et on ne stocke que les impairs. Économise un facteur 2 en mémoire et temps.
- Roue des premiers : on saute les multiples de 2, 3, 5, etc. en utilisant des roues. Économise un facteur ~3.
- Crible segmenté : on découpe N en blocs qui tiennent en cache CPU. Économise un facteur 5-10 sur les très grands N.
- Crible d'Atkin (2003) : crible avancé en O(N / log log N), mais plus complexe.
- Crible parallèle : on distribue les segments sur plusieurs cores CPU.
🔬 Quand le crible cesse-t-il d'être pratique ?
Pour de très grands N (≥ 10¹²), le crible classique devient impraticable car il faut allouer un tableau de N booléens — ce qui ne tient plus en mémoire. À cette échelle, on utilise :
- Crible segmenté : on examine N par tranches de 10⁶ à 10⁸ qui tiennent en mémoire.
- Tests de primalité probabilistes (Miller-Rabin, AKS) : on ne crible plus, on teste un nombre à la fois.
- Index pré-calculés : les premiers ≤ 10¹² sont déjà tabulés et publiquement accessibles.
🌍 Applications : pourquoi on en a besoin
- Cryptographie RSA : génération de premiers de 1024 à 4096 bits. Le crible sert à éliminer rapidement les petits facteurs avant un test plus coûteux.
- Hachage et tables de hachage : on cherche des premiers proches d'une taille cible pour éviter les collisions.
- Théorie des nombres : tester des conjectures (Goldbach, Riemann, premiers jumeaux…) nécessite de connaître les premiers jusqu'à un seuil élevé.
- Compétitions de programmation : Ératosthène est l'un des algorithmes les plus utilisés en compétitions (Olympiades d'informatique, Code Jam, ICPC).
📐 Le lien avec ton programme
Le crible est entièrement accessible au BAC SM :
- Nombres premiers (programme arithmétique 2BAC SM) : définition, propriétés.
- Diviseurs et multiples : le crible repose sur ces notions de base.
- Algorithmique (post-bac, TIPE) : excellent exercice de boucles imbriquées.
- Complexité : compter le nombre d'opérations est un exercice typique.
- Sommes harmoniques : la démonstration de complexité utilise ∑ 1/p, qui relie aux séries du programme analyse.
🎯 Petite curiosité : la table de Curtis (1772)
En 1772, Joseph Curtis a publié à la main une table de tous les premiers ≤ 100 000, calculés au crible d'Ératosthène. Cette table, qui a pris des années à compiler, contient 9 592 premiers.
Aujourd'hui, un programme Python génère la même table en 0.01 seconde. Comparaison des époques : 100 ans de travail manuel ⇔ 10 millisecondes d'ordinateur. L'algorithme est resté identique, seul le calcul a changé.
Vérifie ta compréhension
3 questions courtes pour valider tes acquis. Tu peux réessayer.