Sieve of Sundaram

Therefore the list must be composed of exactly the set of odd prime numbers less than or equal to 2n + 2.

The above obscure-but-commonly-implemented Python version of the Sieve of Sundaram hides the true complexity of the algorithm due to the following reasons: The following Python code in the same style resolves the above three issues, as well converting the code to a prime-counting function that also displays the total number of composite-culling operations: The commented-out line is all that is necessary to convert the Sieve of Sundaram to the Odds-Only Sieve of Eratosthenes; this clarifies that the only difference between these two algorithms is that the Sieve of Sundaram culls composite numbers using all odd numbers as the base values, whereas the Odds-Only Sieve of Eratosthenes uses only the odd primes as base values, with both ranges of base values bounded to the square root of the range.

(The interval [a, b] actually starts at the square of the odd base values, but this difference is negligible for large ranges.)

As the integral of the reciprocal of x is exactly log(x), and as the lower value for a is relatively very small (close to 1, whose logarithm is 0), this is about

Ignoring the constant factor of 1/8, the asymptotic complexity is clearly O(n log(n)).