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 Mr. 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 where:
The remaining numbers are doubled and incremented by one, giving a list of the odd prime numbers below.
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, Sundaram's method crosses out for.

Correctness

If we start with integers from to, the final list contains only odd integers from to. From this final list, some odd integers have been excluded; we must show these are precisely the composite odd integers less than.
Let be an odd integer of the form. Then, is excluded if and only if is of the form, that is. Then we have:
So, an odd integer is excluded from the final list if and only if it has a factorization of the form — 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.

def sieveOfSundaram:
k = int
a = *
for i in range:
j = i
while:
a = 1
j+=1
if n > 2:
print
for i in range:
if a 0:
print