crible de Sundaram

Écrivons les nombres impairs de 3 à 31. Certains se décomposent en produit de deux impairs supérieurs à 1 : 9, 15, 21, 25 et 27. Le crible de Sundaram les repère sans tester chaque nombre l'un après l'autre.

La méthode barre d'abord des indices produits par des suites arithmétiques. Chaque indice barré donne un composé impair. Les indices restants donnent alors 3, 5, 7, 11, 13, 17, 19, 23, 29 et 31, qui sont premiers.

Le crible de Sundaram est une méthode de sélection des nombres premiers impairs. On fixe un entier positif n. Les entiers k de 1 à n représentent les nombres impairs 2k + 1, donc les impairs de 3 à 2n + 1.

On barre tout indice k obtenu avec deux entiers positifs i et j, en prenant i inférieur ou égal à j, dès que la valeur ne dépasse pas n :À i fixé, les valeurs forment une suite arithmétique de raison 2i + 1. Le lien avec les composés impairs vient de l'identité :Chaque indice barré produit donc un nombre impair composé. Réciproquement, tout composé impair se factorise en deux impairs supérieurs à 1 et fournit un tel couple d'indices.

Les indices non barrés donnent exactement les nombres premiers impairs 2k + 1 jusqu'à 2n + 1. Le nombre premier 2 doit être ajouté séparément. Publié en 1934 par Sundaram, mathématicien indien, ce crible offre ainsi une construction élémentaire par complément.

Cherchons les nombres premiers jusqu'à 31. La borne choisie est n = 15 ; les indices sont les entiers de 1 à 15 ; chaque indice k représente l'impair 2k + 1.

1. Avec i = 1, les valeurs 1 + 3j qui ne dépassent pas 15 sont 4, 7, 10 et 13.
2. Avec i = 2 et j au moins égal à 2, seule la valeur 2 + 5j = 12 convient.
3. Dès i = 3 et j = 3, la valeur obtenue est 24 : il n'y a donc plus rien à barrer sous 15.
4. On barre ainsi les indices 4, 7, 10, 12 et 13. Ils représentent respectivement 9, 15, 21, 25 et 27.
5. Les autres indices représentent 3, 5, 7, 11, 13, 17, 19, 23, 29 et 31.

Ces dix nombres sont les nombres premiers impairs inférieurs ou égaux à 31. Pour contrôler le résultat, chacun des cinq nombres barrés se factorise : 9 = 3 × 3, 15 = 3 × 5, 21 = 3 × 7, 25 = 5 × 5 et 27 = 3 × 9. Il faut ajouter 2 pour obtenir tous les nombres premiers jusqu'à 31. La figure matérialise la correspondance entre chaque indice et l'impair associé.

Pour dresser à la main une liste de petits nombres premiers, on choisit d'abord la plus grande valeur impaire visée. Une borne 2n + 1 détermine les indices de 1 à n, puis les suites indiquent ceux qu'il faut barrer.

Pour expliquer pourquoi le crible fonctionne, on associe chaque indice k à 2k + 1. La factorisation des nombres barrés devient alors visible grâce au produit de deux facteurs impairs.

Si l'on veut décider si un seul grand entier est premier, on préfère un test de primalité : un crible construit une liste entière jusqu'à une borne, même lorsque l'on ne cherche qu'un verdict. Pour inclure tous les nombres premiers, on ajoute toujours 2 au résultat du crible de Sundaram.

Le crible d'Eratosthène barre directement les multiples des nombres premiers dans une liste d'entiers. Le crible de Sundaram barre des indices de la forme i + j + 2ij, puis les transforme en impairs. Pour la valeur 9, le premier barre le multiple 9 ; le second barre l'indice 4, car 2 × 4 + 1 = 9.

Un test de primalité répond à une question portant sur un entier donné. Le crible de Sundaram produit tous les nombres premiers impairs jusqu'à une borne. Chercher seulement le statut de 29 illustre un test ; obtenir simultanément 3, 5, 7 et tous les suivants jusqu'à 31 illustre un crible.

La sortie 2k + 1 ne contient jamais le nombre 2. Si une liste prétend donner tous les nombres premiers jusqu'à une borne supérieure ou égale à 2 mais commence à 3, il faut ajouter 2 séparément.

La borne porte sur les indices, pas directement sur les nombres testés. Avec n = 15, le dernier impair représenté est 2 × 15 + 1 = 31, et non 15. Il faut donc convertir la borne avant de construire la liste.

Les entiers i et j commencent à 1. Autoriser 0 ferait barrer des indices associés à des nombres premiers, car l'identité ferait intervenir un facteur égal à 1. La condition i ≤ j évite seulement de produire deux fois le même indice en échangeant les facteurs.

Un indice peut apparaître dans plusieurs suites sans représenter plusieurs nombres. Il suffit de le barrer une fois. La répétition signale simplement qu'un même composé impair possède plusieurs décompositions en facteurs impairs.

Le nombre premier précise la propriété qui caractérise chaque valeur conservée par le crible.

Le nombre composé éclaire la factorisation impaire qui justifie chaque indice barré.

Le crible d'Eratosthène offre une autre construction d'une liste de nombres premiers, fondée sur les multiples.

L'article Ce nombre est-il premier ? prolonge la distinction entre production d'une liste et examen d'un entier.