Dictionnaire de mathématiques récréatives Crible d'Ératosthène

Ératosthène v. 284- v. 192 av. J.-C.

° Crible d'Ératosthène. – Algorithme qui permet d'obtenir la liste des nombres premiers inférieurs à un nombre déterminé. Depuis longtemps, le criblage se fait dans un tableau de nombres en barrant successivement, à la façon d'Ératosthène, les multiples de 2, de 3, de 5, de 7, de 11, de 13, ... demeurés sur le tableau. Voici l’illustration de cet algorithme pour la suite des entiers de 2 à 60 :

	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50	51	52	53	54	55	56	57	58	59	60

On biffe d’abord les nombres divisibles par 2 sauf 2 : 4, 6, 8, 10, ...

	2	3		5		7		9		11		13		15		17		19		21		23		25		27		29
31		33		35		37		39		41		43		45		47		49		51		53		55		57		59

Parmi les nombres qui restent, on biffe les nombres divisibles par 3 sauf 3 : 9, 15, 21, 27, 33, 39, 45, 51, 57.

	2	3		5		7				11		13				17		19				23		25				29
31				35		37				41		43				47		49				53		55				59

Si on excepte, les quatre premières colonnes, on note une régularité dans l’occupation des cases : une colonne complète, une vide, une complète, trois vides, une complète, etc. Parmi les nombres qui restent, on biffe les nombres divisibles par 5 sauf 5 : 25, 35, 55 dont une colonne complète.

	2	3		5		7				11		13				17		19				23						29
31						37				41		43				47		49				53						59

Parmi les nombres qui restent, on biffe le seul nombre divisible par 7 sauf 7 : 49.

	2	3		5		7				11		13				17		19				23						29
31						37				41		43				47						53						59

Pour savoir quand s’arrêter, on calcule la racine carrée du plus grand nombre. La racine carrée de 60 est 7,74. On est assuré qu’aucun nombre qui reste n'est un multiple, puisque le plus petit nombre après 7 est 11 dont le carré est 121. En bref, on s’arrête quand le dernier nombre biffé est seul de cette classe et est un carré. Les nombres qui restent, dans le dernier tableau, sont tous les premiers inférieurs à 60.

Index : E