Sieve of Sundaram
In mathematics, the sieve of Sundaram is a simple deterministic algorithm for finding all the prime numbers up to a specified integer. It was discovered by Indian mathematician S. P. Sundaram in 1934.
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 , Sundaram's method crosses out for .
If we start with integers from 1 to n, the final list contains only odd integers from 3 to . From this final list, some odd integers have been excluded; we must show these are precisely the composite odd integers less than .
Let q be an odd integer of the form . Then, q is excluded if and only if k is of the form , that is . Then we have:
So, an odd integer is excluded from the final list if and only if it has a factorization of the form — which is to say, if it has a non-trivial odd factor. Therefore the list must be composed of exactly the set of odd prime numbers less than or equal to .
- 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[permanent dead link], 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 (PDF) (PhD). Purdue University. pp. 70–72.
- Baxter, Andrew. "Sundaram's Sieve". Topics from the History of Cryptography. MU Department of Mathematics.