Crible de Sundaram

Le tableau de Sundaram est constitué comme un tableau où la colonne numéro ${\displaystyle n}$ a pour premier terme ${\displaystyle (2n+1)^{2}}$ et pour raison ${\displaystyle 2*(2n+1)}$. Chaque colonne commence donc par le carré d'un nombre impair, et tous les carrés de nombres impairs commencent une colonne[3].

Chaque colonne comprend tous les multiples impairs du nombre impair ${\displaystyle (2n+1)}$ dont le carré commence la colonne. En effet pour qu'un nombre soit dans cette colonne, il faut et il suffit qu'il soit de la forme: ${\displaystyle (2n+1)*(2n+1)+k*(4n+2)}$, soit ${\displaystyle (2n+1)*(2n+2k+1)}$ ce qui définit, en faisant varier k, tous les multiples impairs de ${\displaystyle (2n+1)}$[4].

Par construction, le tableau ne contient que des nombres impairs composés, et il les contient tous car tout nombre composé impair s'écrit ${\displaystyle (2n+1)*(2m+1)}$ avec ${\displaystyle n<m+1}$, et figure au moins dans la colonne ${\displaystyle n}$.

Le tableau ci-dessous donne les premières lignes et colonnes construites par cette méthode:

Pour savoir si un nombre impair est premier, il suffit de vérifier s'il est dans le tableau (auquel cas ce nombre n'est pas premier), ou s'il n'y est pas (auquel cas il est premier).

Animation de l'usage du crible de Sundaram pour les nombres premiers entre 3 et 200

L'algorithme du crible de Sundaram commence en listant tous les nombres de 1 à n dans un tableau puis d'éliminer tous ceux de la forme ${\displaystyle i+j+2ij}$, tels que ${\displaystyle i+j+2ij<n}$. Les nombres restants sont doublés puis incrémentés. La liste résultante présente alors tous les nombres premiers allant de 3 à ${\displaystyle 2n+1}$[5] - [6].

Il a été vérifié par D. Abdullah et al en 2018 que l'algorithme du crible de Sundaram est plus lent que l'algorithme du crible d'Ératosthène[7].

• Crible d'Ératosthène
• Crible d'Atkin
• Spirale d'Ulam