Sieve of Sundaram

From Wikipedia, the free encyclopedia

In mathematics, the sieve of Sundaram is a simple deterministic algorithm for finding all prime numbers up to a specified integer. It was discovered by East Indian student S. P. Sundaram from Sathyamangalam in 1934.^[1][2]

[edit] Algorithm

All the values in the form of z = i + j + 2ij are excluded from sequence of natural numbers,

where i = 1, 2, 3, ..., n and j = 1, 2, 3, ..., i.

The remaining numbers are doubled and incremented by one. The resulting sequence represents the sequence of odd primes (i.e., all primes except the only even prime 2).

[edit] See also

• Primality test
• General number field sieve
• Sieve theory

[edit] References

1. ^ V. Ramaswami Aiyar (1934). "Sundaram's Sieve for Prime Numbers". The Mathematics Student 2: 73. ISSN 0025-5742. 
2. ^ G. (1941). "Curiosa 81. A New Sieve for Prime Numbers". Scripta Mathematica 8: 164. 

• Ogilvy, C. Stanley; John T. Anderson. Excursions in Number Theory. Dover Publications, 1988 (reprint from Oxford University Press, 1966), pp. 98-100, 158. ISBN 0486257789. 
• Honsberger, Ross (1970). Ingenuity in Mathematics, New Mathematical Library #23. Mathematical Association of America, pp. 75. ISBN 0394709233. 
• A new "sieve" for primes, an excerpt from Kordemski, Boris A. (1974). Köpfchen, Köpfchen! Mathematik zur Unterhaltung, MSB Nr. 78. Urania Verlag, pp. 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: 70-72, Purdue University. 
• Baxter, Andrew. "Sundaram’s Sieve". Topics from the History of Cryptography. MU Department of Mathematics. 

v • d • e Number-theoretic algorithms Primality tests AKS · APR · Ballie-PSW · ECPP · Fermat · Lucas–Lehmer · Lucas–Lehmer (Mersenne numbers) · Lucas–Lehmer–Riesel · Proth's theorem · Pépin's · Solovay-Strassen · Miller-Rabin · Trial division Sieving algorithms Sieve of Atkin · Sieve of Eratosthenes · Sieve of Sundaram · Wheel factorization Integer factorization algorithms CFRAC · Dixon's · ECM · Euler's · Pollard's rho · P - 1 · P + 1 · QS · GNFS · SNFS · rational sieve · Fermat's · Shanks' square forms · Trial division · Shor's algorithm Other algorithms Ancient Egyptian multiplication · Aryabhata · Binary GCD · Chakravala · Euclidean · Extended Euclidean · integer relation algorithm · integer square root · Modular exponentiation · Shanks-Tonelli Italics indicate that algorithm is for numbers of special forms; bold indicates deterministic algorithm for primality tests.