# Time complexity of Sieve of Eratosthenes [closed]

Wikipedia states that the Sieve of Eratosthenes runs in time $$O(n\log\log n)$$. Why is that so?

• Follow the algorithm and see how many operations it will perform. It is "a direct consequence of the fact that the prime harmonic series asymptotically approaches log log n – gnasher729 Jul 29 '19 at 11:41
• At least you should be able to write the number of operations as a sum. – gnasher729 Jul 29 '19 at 12:00
• @gnasher729 Why prime harmonic series asymptotically approaches log log n ? I have read the proof on that link, but I am still confused. – kevin Jul 29 '19 at 12:51

Now instead of adding 1/k for $$2^m ≤ k < 2^{m+1}$$ you add 1/k for only the primes k with $$2^m ≤ k < 2^{m+1}$$. How many are there? What sum do you get now? And then you have a sum that looks almost exactly like the one you started with and gives you the result.