- Sieve of Sundaram
In

mathematics , the**sieve of Sundaram**is a simpledeterministic algorithm for finding allprime number s up to a specified integer. It was discovered by an Indian student S. P. Sundaram fromSathyamangalam in 1934. [*cite journal |author=V. Ramaswami Aiyar |title=Sundaram's Sieve for Prime Numbers |journal=The Mathematics Student |volume=2 |number=2 |year=1934 |pages=73 |issn=0025-5742*] [*cite journal |author=G.|title=Curiosa 81. A New Sieve for Prime Numbers |journal=*]Scripta Mathematica |volume=8 |number=3 |year=1941 |pages=164**Algorithm**A list of the positive integers is made. From this list, remove all numbers of the form of "i" + "j" + 2"ij" where "i" and "j" are positive integers (and "j" <= "i", to exclude trivial duplicates).

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" + 2"ij" is doubled and incremented, we have

2("i" + "j" + 2"ij") + 1

= 2"i" + 2"j" + 4"ij" + 1

= (2"i" + 1)(2"j" + 1).

Thus all the numbers excluded from the doubled-and-incremented list are composite, because both factors in (2"i" + 1)(2"j" + 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.

**ee also***

Primality test

*General number field sieve

*Sieve theory **References***

*

* [*http://www.primzahlsuche.de/intro.html#sieve2 A new "sieve" for primes*] , an excerpt from cite book |last=Kordemski |first=Boris A. |title=Köpfchen, Köpfchen! Mathematik zur Unterhaltung|publisher=Urania Verlag| year=1974 |series=MSB Nr. 78 | pages=pp. 200 (translation of Russian book cite book |last=Кордемский |first=Борис Анастасьевич |title=Математическая смекалка |publisher=М.: ГИФМЛ |year=1958 |url=http://ilib.mirror1.mccme.ru/djvu/klassik/smekalka.htm)

*

*

*

*Wikimedia Foundation.
2010.*