Voir la source de Crible d'Ératosthène

{{Voir homonymes|Ératosthène (homonymie)}}

Le '''crible d'[[Ératosthène]]''' est un procédé qui permet de trouver tous les [[nombre premier|nombres premiers]] inférieurs à un certain [[entier naturel]] donné ''N''. Le [[crible d'Atkin]] est plus rapide mais plus complexe.

== Algorithme ==

L'algorithme procède par élimination : il s'agit de supprimer d'une table des entiers de 2 à N tous les [[multiple (mathématiques)|multiples]] d'un entier (autres que lui-même).  

En supprimant tous ces multiples, à la fin il ne restera que les entiers qui ne sont multiples d'aucun entier à part 1 et eux-mêmes, et qui sont donc les nombres premiers.

On commence par rayer les multiples de 2, puis les multiples de 3 restants, puis les multiples de 5 restants, et ainsi de suite en rayant à chaque fois tous les multiples du plus petit entier restant.

On peut s'arrêter lorsque le carré du plus petit entier restant est supérieur au plus grand entier restant, car dans ce cas, tous les non-premiers ont déjà été rayés précédemment.

À la fin du processus, tous les entiers qui n'ont pas été rayés sont les nombres premiers inférieurs à N.

L'animation ci-dessous illustre le crible d'Ératosthène pour N=120 :
[[Image:New Animation Sieve of Eratosthenes.gif|thumb|upright=2|center]]Remarque: si un nombre n est [[Nombre composé|composé]], alors n=n<sub>1</sub>n<sub>2</sub>, avec nécessairement l'un au moins des diviseurs n<sub>i</sub> plus petit que <math>\sqrt{n}</math>. C'est pourquoi dans le crible ci-dessus, pour chaque nombre premier trouvé, la suppression commence par le carré de celui-ci. À partir de 11, on devrait donc démarrer à 121=11², au-delà de la taille choisie 120, il n'y a donc plus aucune suppression après avoir trouvé les multiples de 7.

== Exemples de mise en œuvre informatique ==

Le crible d'Ératosthène peut être mis en œuvre de façon classique ou [[Récursivité|récursive]], mais aussi sous la forme d'une [[Pipeline (architecture des processeurs)|méthode pipe-line]].

=== Pseudo-code ===
On peut transcrire l'algorithme en utilisant un [[tableau (structure de données)|tableau]] de [[booléen]]s<ref>Adapté d'un programme en C dans {{ouvrage|lang=en|auteur=Robert Sedgewick |titre=Algorithms in C, parts 1-4 |sous-titre=fundamentals, data structure, sorting, searching |année=1998 |éditeur=Addison-Wesley |isbn=0-201-31452-5 |numéro édition=3}}, {{p.|84}}.</ref> :

 ''Crible d'Ératosthène''
     '''entrée :''' N > 1 entier
     '''sortie :''' la liste de tous les nombres premiers <= N
     L = tableau de booléens de taille N, initialisés à Vrai
     L[1] = Faux
     '''Pour''' i de 2 à N
         '''Si''' L[i]
             '''Pour''' j allant de i*i à N par pas de i
             ''on peut commencer à i*i car tous les multiples de i inférieurs à i*i ont déjà été rayés''
                 L[j] = Faux
             '''Fin pour'''
         '''Fin si'''
     '''Fin pour'''
     '''Retourner''' La liste des i de 2 à N tels que L[i] est vrai
 '''Fin fonction'''

Dès que i*i>N la boucle intérieure ('''Pour''' j) est vide :  on aurait pu prendre i de 2 à la [[partie entière]] de {{sqrt|N}} , après avoir calculé ce nombre. On peut aussi éviter de cocher plusieurs fois les nombres pairs et diviser le temps d'exécution par 2, en passant à un incrément de 2*i pour j dès que i > 2.

Le temps d'exécution est clairement proportionnel à :
:{{math|''N'' + ''N''/2  + ''N''/3 + ''N''/5 + ''N''/7 + ''N''/11 + ⋯}}
qui est lui même très inférieur à {{mvar|N}}<sup>3/2</sup>{{sfn|Sedgewick|1998|p=84}}.

On aurait un programme plus efficace en espace en utisant des tableaux de [[bit]]s plutôt que des booléens{{sfn|Sedgewick|1998|p=84}} (soit en utilisant des tableaux d'[[entier (informatique)|entiers]] et les [[opération bit à bit|opérations bit à bit]]).

=== Version pipe-line : le crible de [[Charles Antony Richard Hoare|Hoare]] (1978) ===
L'idée est d'engendrer chaque nombre à vérifier, pour le soumettre à un tri en cascade, ne conservant des entiers reçus que ceux qui sont premiers.

Pour cela, à chaque nombre premier repéré est associé un poste qui ne transmettra parmi ses successeurs que ceux qui ne sont pas ses multiples.

Ce système n'utilise pas de table ou de liste de nombres à traiter ''a priori'', mais à tout moment ''un poste'' (cellule active ou ''[[coroutine]]'') ''par nombre premier déjà reconnu''.
<pre>
Crible de C.A.R HOARE :

Un GENERATEUR passe chaque entier de 2 à N au premier poste disponible(qu'il crée s'il n'existe pas).

Pour chaque POSTE créé :
* il conserve le premier entier qu'il reçoit, disons p, 
* puis il transmet au poste suivant (créé si besoin) tout entier reçu n non divisible par p.
</pre>
Ainsi : 
*2 crée le poste 2
*3 passe le poste 2 et crée le poste 3
*4 est intercepté par le poste 2
*5 passe les postes 2 et 3, et crée le poste 5
*6 est intercepté par le poste 2
*7 passe les postes 2, 3, 5, et crée le poste 7
*...
*36 est intercepté par le poste 2,
*37 passe les postes 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, et crée le poste 37...

En régime de croisière, '''''ce crible commence à vérifier la primalité de nouveaux nombres pendant qu'il poursuit ou achève la vérification de la primalité de nombres précédents'''''.

Nous noterons, qu'à moins de disposer d'une machine parallèle avec <math>\sqrt{n}</math> processeurs, cette méthode est inefficace puisque chaque poste parcourt un nombre d'entiers de l'ordre de n.

== Notes et références ==
{{Références}}
* C. A. R. Hoare, ''Communicating sequential processes'', CACM 21 (1978) {{p.|666-677}}
* Κόσκινον Ερατοσθένους ''or, The Sieve of Eratosthenes. Being an Account of His Method of Finding All the Prime Numbers'', by the Rev. Samuel Horsley, F. R. S., Philosophical Transactions (1683-1775), Vol. 62. (1772), {{p.|327-347}}.

== Annexes ==
=== Articles connexes ===
*[[Crible de Sundaram]]
*[[Crible d'Atkin]]
*[[Spirale d'Ulam]]
*[[Nombre chanceux]]
*[[Divisions successives]]
*[[Densité asymptotique|Densité]]

=== Liens externes ===
* {{lien web |auteur1=Rolf H. Möhring |auteur2=Martin Oellrich |auteur3=Robert Pankrath |titre=Le crible d'Ératosthène |date=2009 |éditeur=[[inria]] |url=https://interstices.info/le-crible-deratosthene/}}.

{{Portail|arithmétique|informatique théorique}}

[[Catégorie:Test de primalité]]
[[Catégorie:Nombre premier]]
[[Catégorie:Théorie des cribles]]