Sieve of Sundaram

The sieve of Sundaram is a simple deterministic algorithm for finding all the prime numbers up to a specified integer, and a variant of the sieve of Eratosthenes. It was discovered in 1934 by the Indian student S. P. Sundaram. The sieve starts with the integers from 1 to n and removes every number of the form i + j + 2ij, where i and j are positive integers with i not greater than j and the result not above n. The numbers that remain are doubled and increased by one, which gives the odd primes below 2n + 2. Even numbers are never considered, because the work of crossing out the multiples of 2 is done by the final double-and-increment step. An odd integer is excluded exactly when it has a nontrivial odd factorization of the form (2i + 1)(2j + 1), which proves the method correct. Implemented properly it performs many more culling operations than the sieve of Eratosthenes, and its asymptotic complexity is O(n log n).