Sieve of Sundaram
In mathematics, the sieve of Sundaram is a simple deterministic algorithm for finding all prime numbers up to a specified integer. It was discovered in 1934 by S. P. Sundaram, an Indian student from Sathyamangalam.
Start with a list of the integers from 1 to n. From this list, remove all numbers of the form i + j + 2ij where:
The remaining numbers are doubled and incremented by one, giving a list of the odd prime numbers (i.e., all primes except 2) below 2n + 2.
The sieve of Sundaram sieves out the composite numbers just as sieve of Eratosthenes does, but even numbers are not considered; the work of "crossing out" the multiples of 2 is done by the final double-and-increment step. Whenever Eratosthenes' method would cross out k different multiples of a prime 2i+1, Sundaram's method crosses out i + j(2i+1) for .
The final list of doubled-and-incremented integers contains only odd integers; we must show that the set of odd integers excluded from the list is exactly the set of composite odd integers.
An odd integer is excluded from the final list if and only if it is of the form 2(i + j + 2ij) + 1, and we have
- 2(i + j + 2ij) + 1
- = 2i + 2j + 4ij + 1
- = (2i + 1)(2j + 1).
So, an odd integer is excluded from the final list if and only if it has a factorization of the form (2i + 1)(2j + 1) — which is to say, if it has a non-trivial odd factor. Since every odd composite number has a non-trivial odd factor, we may safely say that an odd integer is excluded from the final list if and only if it is composite. Therefore the list must be composed of exactly the set of odd prime numbers less than or equal to 2n + 2.
The sieve of Sundaram finds the primes less than n in O(n log n) operations using O(n) bits of memory.. This is when one uses a simplistic approach for ordering with a traditional sorting algorithm. Possible algorithmic efficiency improvements in prime generation exist with the use of a simple hashtable and indefinite loop. Such structures will produce a sieve which finds the primes less than n in O(n) when one assumes that hashtable access times are O(1).
- Ogilvy, C. Stanley; John T. Anderson (1988). Excursions in Number Theory. Dover Publications, 1988 (reprint from Oxford University Press, 1966). pp. 98–100, 158. ISBN 0-486-25778-9.
- Honsberger, Ross (1970). Ingenuity in Mathematics. New Mathematical Library #23. Mathematical Association of America. p. 75. ISBN 0-394-70923-3.
- A new "sieve" for primes, an excerpt from Kordemski, Boris A. (1974). Köpfchen, Köpfchen! Mathematik zur Unterhaltung. MSB Nr. 78. Urania Verlag. p. 200. (translation of Russian book Кордемский, Борис Анастасьевич (1958). Математическая смекалка. М.: ГИФМЛ.)
- Movshovitz-Hadar, N. (1988). "Stimulating Presentations of Theorems Followed by Responsive Proofs". For the Learning of Mathematics 8 (2): 12–19.
- Ferrando, Elisabetta (2005). "Abductive processes in conjecturing and proving". Ph.D. theses. Purdue University. pp. 70–72.
- Baxter, Andrew. "Sundaram’s Sieve". Topics from the History of Cryptography (MU Department of Mathematics).