Go back

Prime number

Last updated: Mon May 12 2025

I came across a LeetCode problem: Count the Number of Primes. Initially, I knew the brute-force solution, which involves checking all numbers up to n. I was also aware of the basic optimization where it’s sufficient to check up to √n for which the time complexity is O(√n). However, after reading the editorial, I discovered that the solution can be further optimized using the Sieve of Eratosthenes, achieving a time complexity of O(n log log n). Here’s the analysis:

Count Primes - LeetCode

Solution

def countPrimes(self, n: int) -> int:
        if n < 2:
            return 0
        is_prime = [True] * n
        is_prime[0] = is_prime[1] = False
        
        for i in range(2 , int(n ** 0.5) + 1):
            if is_prime[i]:
                for j in range(i*i, n, i):
                    is_prime[j] = False
                    
        return sum(is_prime)

Analysis of Sieve of Eratosthenes

For math lovers,

Estimate the total number of assignments is_prime[j]=Falseis\_prime[j] = \text{False} over all iterations of:

for i in range(2, √n):
    if is_prime[i]:
        for j in range(i*i, n, i):
            ...

1: Inner Loop Analysis (Per i)

When i is prime, we mark off multiples of i starting from i2i^2 up to <n< n.

So for a fixed i, the number of iterations is:

⌊n−i2i⌋+1=⌊ni−i⌋+1\left\lfloor \frac{n - i^2}{i} \right\rfloor + 1 = \left\lfloor \frac{n}{i} - i \right\rfloor + 1

Let’s denote this as:

T(i)=⌊ni−i⌋+1T(i) = \left\lfloor \frac{n}{i} - i \right\rfloor + 1

2: Number of Operations

We only run the inner loop for prime values of i from 22 to n\sqrt{n}.

Let π(x)\pi(x) be the number of primes less than or equal to x. Then:

∑i=2i primenT(i)≈∑i=2n(ni−i)\sum_{\substack{i=2 \\ i \text{ prime}}}^{\sqrt{n}} T(i) \approx \sum_{i=2}^{\sqrt{n}} \left( \frac{n}{i} - i \right)

We simplify:

∑i=2n(ni−i)=n∑i=2n1i−∑i=2ni\sum_{i=2}^{\sqrt{n}} \left( \frac{n}{i} - i \right) = n \sum_{i=2}^{\sqrt{n}} \frac{1}{i} - \sum_{i=2}^{\sqrt{n}} i

3: Estimate Harmonic Sum

The harmonic sum up to n\sqrt{n} is approximately:

∑i=2n1i≈ln⁡(n)=12ln⁡(n)\sum_{i=2}^{\sqrt{n}} \frac{1}{i} \approx \ln(\sqrt{n}) = \frac{1}{2} \ln(n)

And the sum of integers from 22 to n\sqrt{n} is:

∑i=2ni=n(n+1)2−1≈n2\sum_{i=2}^{\sqrt{n}} i = \frac{\sqrt{n}(\sqrt{n} + 1)}{2} - 1 \approx \frac{n}{2}

4: Combine Terms

Putting it together:

Total ops≈n⋅12ln⁡n−n2=O(nlog⁡n)\text{Total ops} \approx n \cdot \frac{1}{2} \ln n - \frac{n}{2} = O(n \log n)

But this is an overestimate, because we’re summing over all i, not just the primes.

So we correct the estimate:

∑i=2i primenni≈n⋅∑p≤n1p\sum_{\substack{i=2 \\ i \text{ prime}}}^{\sqrt{n}} \frac{n}{i} \approx n \cdot \sum_{p \le \sqrt{n}} \frac{1}{p}

And the sum of reciprocals of primes up to x is known to be:

∑p≤x1p≈ln⁡ln⁡x\sum_{p \le x} \frac{1}{p} \approx \ln \ln x

Let $x = \sqrt{n}$, then:

ln⁡ln⁡n=ln⁡(12ln⁡n)=ln⁡ln⁡n+ln⁡12\ln \ln \sqrt{n} = \ln\left(\frac{1}{2} \ln n\right) = \ln \ln n + \ln \frac{1}{2}

Which simplifies to:

∑p≤nnp≈nln⁡ln⁡n\sum_{p \le \sqrt{n}} \frac{n}{p} \approx n \ln \ln n

Conclusion

O(nlog⁡log⁡n)\boxed{O(n \log \log n)}

Inner Loop Analysis

Counting Steps in the Sieve of Eratosthenes Inner Loop

We want to show:

⌊n−i2i⌋+1=⌊ni−i⌋+1\left\lfloor \frac{n - i^2}{i} \right\rfloor + 1 = \left\lfloor \frac{n}{i} - i \right\rfloor + 1

This expression counts the number of steps in the loop:

for j in range(i * i, n, i):

Algebraic Derivation

Start with the left-hand side:

⌊n−i2i⌋+1\left\lfloor \frac{n - i^2}{i} \right\rfloor + 1

Break it apart:

=⌊ni−i2i⌋+1=⌊ni−i⌋+1= \left\lfloor \frac{n}{i} - \frac{i^2}{i} \right\rfloor + 1 = \left\lfloor \frac{n}{i} - i \right\rfloor + 1

So both expressions are equal:

⌊n−i2i⌋+1=⌊ni−i⌋+1\left\lfloor \frac{n - i^2}{i} \right\rfloor + 1 = \left\lfloor \frac{n}{i} - i \right\rfloor + 1

Example

Let:

n=20,i=3,i2=9n = 20, \quad i = 3, \quad i^2 = 9

The loop:

for j in range(9, 20, 3)

Produces:

[9,12,15,18](4 elements)[9, 12, 15, 18] \quad \text{(4 elements)}

Left-hand side:

⌊20−93⌋+1=⌊113⌋+1=⌊3.666⌋+1=3+1=4\left\lfloor \frac{20 - 9}{3} \right\rfloor + 1 = \left\lfloor \frac{11}{3} \right\rfloor + 1 = \left\lfloor 3.666 \right\rfloor + 1 = 3 + 1 = 4

Right-hand side:

⌊203−3⌋+1=⌊6.666−3⌋+1=⌊3.666⌋+1=3+1=4\left\lfloor \frac{20}{3} - 3 \right\rfloor + 1 = \left\lfloor 6.666 - 3 \right\rfloor + 1 = \left\lfloor 3.666 \right\rfloor + 1 = 3 + 1 = 4

Conclusion

The two expressions are mathematically equivalent:

⌊n−i2i⌋+1=⌊ni−i⌋+1\left\lfloor \frac{n - i^2}{i} \right\rfloor + 1 = \left\lfloor \frac{n}{i} - i \right\rfloor + 1

They both count how many times the loop executes for a given i in the Sieve of Eratosthenes.