The Sieve of Eratosthenes finds all prime numbers up to n in:

Concept: The Sieve of Eratosthenes finds all primes up to n by, for every prime p, crossing off every multiple of p in the range. The total number of crossing-off operations is the sum of n/p over all primes p up to n. By a classical number-theory result (related to Mertens' second theorem), the sum of reciprocals of the primes up to n, i.e. Σ(1/p), grows as Θ(log log n). Multiplying this growth by the n candidates gives the standard result: the sieve runs in Θ(n log log n) time.

Application: Apply this to the sieve's own operation:

1. For each prime p (2, 3, 5, 7, 11, ...) up to n, the algorithm marks every multiple of p (i.e. 2p, 3p, 4p, ...) as composite.

2. The number of multiples of p marked in the range up to n is n/p, so the total work across all primes is n/2 + n/3 + n/5 + n/7 + ... = n times the sum of 1/p over all primes p up to n.

3. That sum of reciprocals of primes, Σ(1/p), is a well-known asymptotic quantity that grows as Θ(log log n) -- much slower than the harmonic series over all integers.

4. Multiplying the n factor by this Θ(log log n) growth gives the sieve's total running time: Θ(n log log n).

Cross-check: This bound sits exactly where it should relative to the other offered options: it must be worse than O(log n) or O(1) alone (the algorithm has to touch cells across the whole range up to n, so it cannot be purely logarithmic or constant), yet it is much better than a naive O(n2) trial-division sieve, because log log n grows extremely slowly (for example, log log(109) is only about 3). This confirms O(n log log n) as the distinctly correct, well-known complexity class for this algorithm.

Result: The time complexity of the Sieve of Eratosthenes to find all primes up to n is O(n log log n).