Re: The computational complexity of the Sieve of Eratosthenes

Juha Nieminen said:

<snip>

[...] 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.

--
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