#191 / 200•Foundations•MathTCG #191 / 500•★Commune•ℤArithmétique•Méthode & Idée

Crible d'Ératosthène

Période historique : IIIe siècle av. J.-C.

L'algorithme de filtrage millénaire pour lister tous les nombres premiers jusqu'à N en biffant les multiples.

Contenu & Formulation mathématique

Principe de la démarche

Éliminer itérativement tous les multiples stricts des nombres premiers déjà identifiés jusqu'à la racine carrée de N.

Champs d'application canoniques

Génération de tables de nombres premiers, cryptanalyse préliminaire et benchmarking de processeurs.

k \cdot p \notin \mathbb{P} \quad (p \in \mathbb{P}, \; k \ge 2, \; p^2 \le N)

Genèse & Portée historique

Méthode arithmétique simple et efficace permettant de trouver tous les nombres premiers inférieurs à une limite fixée N. En éliminant successivement les multiples de chaque nombre premier découvert à partir de 2, les nombres survivants sont exactement les nombres premiers.

Les Grecs anciens traçaient la table des nombres sur une tablette de papyrus ou de cire et perçaient d'un trou chaque multiple composé éliminé, la tablette finale ressemblant à un tamis ou un crible à grains.

« Secouer la grille des entiers : seuls les atomes premiers refusent de tomber à travers les mailles. »