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 an Indian student S. P. Sundaram from Sathyamangalam in 1934.[1][2]
Contents |
Algorithm
Start with a list of the integers from 1 to n. From this list, remove all numbers of the form of i + j + 2ij where:
(which can be found by manipulating n ≥ i + j + 2ij)
The remaining numbers are doubled and incremented by one, giving a list of the odd prime numbers (i.e., all primes except the only even prime 2).
Correctness
If the expression i + j + 2ij is doubled and incremented, we have
2(i + j + 2ij) + 1
= 2i + 2j + 4ij + 1
= (2i + 1)(2j + 1).
Thus all the numbers excluded from the doubled-and-incremented list are composite, because both factors in (2i + 1)(2j + 1) are greater than 1. If a number is prime, it cannot be placed into that factorization for any positive i, j, and so is left in the list.
Computational complexity
The sieve of Sundaram finds the primes less than n in Θ(n log n) operations using Θ(n) bits of memory.
See also
References
- ^ V. Ramaswami Aiyar (1934). "Sundaram's Sieve for Prime Numbers". The Mathematics Student 2 (2): 73. ISSN 0025-5742.
- ^ G. (1941). "Curiosa 81. A New Sieve for Prime Numbers". Scripta Mathematica 8 (3): 164.
- 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 0486257789. http://books.google.com/books?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). Математическая смекалка. М.: ГИФМЛ. http://ilib.mccme.ru/djvu/klassik/smekalka.htm.)
- 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. http://proxy.sv.inge.unige.it/SMA/Sv/AbPCP.pdf.
- Baxter, Andrew. "Sundaram’s Sieve". Topics from the History of Cryptography (MU Department of Mathematics).
|
||||||||||||||||||||||||||
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
