Search code examples
primessieve-algorithm

Sieve Of Eratosthenes in O(n)

I recently came across an article that claimed that it can find all primes less than n in O(n) using an efficient Sieve Of Eratosthenes. However I am unable to see how it is O(n).

https://www.geeksforgeeks.org/sieve-eratosthenes-0n-time-complexity/

Could anyone please help with that?

Solution

  • The normal Sieve of Eratosthenes is O(n log log n).

    Paul Pritchard has done some work on sieves similar to the Sieve of Eratosthenes that run in O(n) and even in O(n / log log n). They are tricky to implement, and despite improved theoretical time complexity, the bookkeeping involved in running the sieves makes them slower than the normal Sieve of Eratosthenes.

    I discuss a simple version of Pritchard's sieve at my blog.