Crible de Sundaram
Le crible de Sundaram permet de lister les entiers naturels impairs composés grâce à des suites arithmétiques placées en colonnes. Son intérêt est qu'on peut en déduire, par passage au complémentaire, l'ensemble des nombres premiers.
S. P. Sundaram était un mathématicien indien originaire de la ville de Sathyamangalan dans l'état du Tamil Nadu. La méthode et le tableau qu'il publia en 1934[1],[2] donnaient toutes les valeurs telles que ne soit pas premier. Une méthode algorithmique de cette approche offre directement les valeurs des nombres premiers impairs.
Tableau de Sundaram
Le tableau de Sundaram est constitué comme un tableau où la colonne numéro a pour premier terme et pour raison . 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 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: , soit ce qui définit, en faisant varier k, tous les multiples impairs de [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 avec , et figure au moins dans la colonne .
Le tableau ci-dessous donne les premières lignes et colonnes construites par cette méthode :
9 | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
15 | 25 | ||||||||||
21 | 35 | 49 | |||||||||
27 | 45 | 63 | 81 | ||||||||
33 | 55 | 77 | 99 | 121 | |||||||
39 | 65 | 91 | 117 | 143 | 169 | ||||||
45 | 75 | 105 | 135 | 165 | 195 | 225 | |||||
51 | 85 | 119 | 153 | 187 | 221 | 255 | 289 | ||||
57 | 95 | 133 | 171 | 209 | 247 | 285 | 323 | 361 | |||
63 | 105 | 147 | 189 | 231 | 273 | 315 | 357 | 399 | 441 | ||
69 | 115 | 161 | 207 | 253 | 299 | 345 | 391 | 437 | 483 | 529 | |
... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... |
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).
Algorithme
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e0/Sieve_of_Sundaram_Animated.gif/220px-Sieve_of_Sundaram_Animated.gif)
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 , tels que . Les nombres restants sont doublés puis incrémentés. La liste résultante présente alors tous les nombres premiers allant de 3 à [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].
Justification
Excepté 2, tous les nombres premiers sont impairs. On prend alors q, un nombre premier impair de la forme . Si vérifie la condition du crible ( soit ), alors
Ainsi, n'est pas un nombre premier. Les nombres subsistants sont alors des nombres premiers[5].
Notes et références
- ↑ (en) V. Ramaswami Aiyar, « Sundaram's Sieve for Prime Numbers », The Mathematics Student, vol. 2, no 2, , p. 73 (ISSN 0025-5742, lire en ligne).
- ↑ (en) G., « Curiosa 81. A New Sieve for Prime Numbers », Scripta Mathematica, vol. 8, no 3, , p. 164 (lire en ligne).
- ↑ (en) C. Stanley Ogilvy et John T. Anderson, Excursions in number theory, New York, Dover Publications, , 183 p. (ISBN 978-0-486-25778-5, lire en ligne), p. 98-99, 158
- ↑ Un même nombre peut apparaitre plusieurs fois dans le résultat du crible. Par exemple, 45 = 9 × 5 apparait dans les colonnes commençant par 9 et 25.
- ↑ a et b Gérard Villemin, « Crible de Sundaram », sur Nombres : Curiosités - Théorie - Usage, (consulté le )
- ↑ (en) « Sieve of Sundaram », sur Art of Problem Solving (consulté le )
- ↑ (en) D Abdullah, R Rahim, D Apdilah, S Efendi, T Tulus et S Suwilo, « Prime Numbers Comparison using Sieve of Eratosthenes and Sieve of Sundaram Algorithm », 2nd International Conference on Computing and Applied Informatics, (lire en ligne, consulté le ).
Articles connexes
- Crible d'Ératosthène
- Crible d'Atkin
- Spirale d'Ulam
Arithmétique et théorie des nombres