Re: The computational complexity of the Sieve of Eratosthenes

Juha Nieminen said:

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.

You have to bear in mind, of course, that the Wikipedia page could be
wrong, as they so often are.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
.

Relevant Pages