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?

closed as unclear what you're asking by xskxzr, dkaeae, Evil, Yuval Filmus, JuhoSep 13 at 9:50

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• 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 at 11:41
• At least you should be able to write the number of operations as a sum. – gnasher729 Jul 29 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 at 12:51
• Doesn't the Wikipedia page contain the answer? – xskxzr Aug 29 at 11:45

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.