Re: The computational complexity of the Sieve of Eratosthenes

On Apr 29, 4:58 am, Juha Nieminen <nos...@xxxxxxxxxxxxxx> wrote:
Richard Heathfield wrote:
[...] The wikipedia page gives a
complexity of O((n log n)(log log n)) for the [Sieve of
Eratosthenes] algorithm. Where does this come from?

Without looking /too/ closely at it, I would guess that it has to do with
the fact that the number of primes less than n is, to a first
approximation, n / log n.

  If pi(n) is O(n/log n), then O(sqrt(n*pi(n))) becomes
O(sqrt(n*n/log n)) = O(n/sqrt(log n)).

  I still don't get where the O((n log n)(log log n)) is coming from.

I think all of these answers are wrong.

Look in here:
http://www.shoup.net/ntb/ntb-v1.pdf

Merten's theorem is used to prove complexity of the Sieve or
Eratosthenes.

Anyway, there are much better sieves now like the Sieve of Aitken.
.

Relevant Pages