TOPICS
Search

Sundaram's Sieve


Sundaram's sieve is an algorithm for finding all odd primes up to a given bound. Start with the integers from 1 to n and cross out every number of the form i+j+2ij for positive integers i<=j. For each remaining number k, output 2k+1. This gives all odd primes through 2n+1. Include 2 separately to obtain all primes through that bound (Havil 2009).

The sieve works because

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

Every crossed-out number therefore corresponds to an odd composite number. Conversely, each odd composite number is a product of two odd factors greater than 1, which can be written as 2i+1 and 2j+1 with 1<=i<=j.

For example, take n=12. For i=1, cross out 4, 7, and 10. For i=2, cross out 12. For i>=3, the smallest value possible is 24. The surviving indices are 1, 2, 3, 5, 6, 8, 9, and 11, giving the odd primes 3, 5, 7, 11, 13, 17, 19, and 23.

The first few terms of the array i+j+2ij read by antidiagonals are 4, 7, 7, 10, 12, 10, ... (OEIS A159919).


See also

Prime Number, Sieve, Sieve of Eratosthenes

Explore with Wolfram|Alpha

References

Havil, J. "Sundaram's Sieve." Plus. Mar. 1, 2009. https://plus.maths.org/sundarams-sieve.Sloane, N. J. A. Sequence A159919in "The On-Line Encyclopedia of Integer Sequences."

Cite this as:

Weisstein, Eric W. "Sundaram's Sieve." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/SundaramsSieve.html

Subject classifications