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.

Algorithm

Start with a list of the integers from 1 to n. From this list, remove all numbers of the form i + j + 2ij where:

• $i,j\in \mathbb {N} ,\ 1\leq i\leq j$ • $i+j+2ij\leq n$ 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 $2i+1$ , Sundaram's method crosses out $i+j(2i+1)$ for $1\leq j\leq \lfloor k/2\rfloor$ .

Correctness

If we start with integers from 1 to n, the final list contains only odd integers from 3 to $2n+1$ . From this final list, some odd integers have been excluded; we must show these are precisely the composite odd integers less than $2n+2$ .

Let q be an odd integer of the form $2k+1$ . Then, q is excluded if and only if k is of the form $i+j+2ij$ , that is $q=2(i+j+2ij)+1$ . Then we have:

{\begin{aligned}q&=2(i+j+2ij)+1\\&=2i+2j+4ij+1\\&=(2i+1)(2j+1).\end{aligned}} So, an odd integer is excluded from the final list if and only if it has a factorization of the form $(2i+1)(2j+1)$ — 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 $2n+2$ .