Problem Description

Given an integer n, you need to count how many prime numbers exist that are strictly less than n.

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. For example, 2, 3, 5, 7, 11 are prime numbers, while 4, 6, 8, 9 are not prime.

The solution uses the Sieve of Eratosthenes algorithm, which is an efficient method for finding all primes up to a given number:

1. Create a boolean array primes of size n, initially marking all numbers as potentially prime (True)
2. Start iterating from 2 (the smallest prime number) up to n-1
3. For each number i:
   • If primes[i] is still True, it's a prime number, so increment the counter
   • Mark all multiples of i (starting from 2i, 3i, 4i, ...) as non-prime by setting them to False
4. Return the total count of prime numbers found

The key insight is that if a number i is prime, then all its multiples (2i, 3i, 4i, etc.) cannot be prime. By systematically eliminating these multiples, we efficiently identify all prime numbers less than n.

For example, if n = 10:

• Prime numbers less than 10 are: 2, 3, 5, 7
• The function would return 4

Intuition

The naive approach would be to check each number from 2 to n-1 individually to see if it's prime. For each number, we'd need to check if it has any divisors, which would take O(n * sqrt(n)) time overall. This becomes inefficient for large values of n.

The key observation is that we can leverage the relationship between prime numbers and their multiples. Once we identify a number as prime, we immediately know that all its multiples cannot be prime. For instance, if we know 2 is prime, we can immediately mark 4, 6, 8, 10... as non-prime without checking them individually.

This leads us to think about a "marking" or "elimination" strategy: instead of checking if each number is prime, we can start with the assumption that all numbers might be prime, then systematically eliminate the non-primes.

The process works like finding prime numbers on a number line: when we encounter a prime number i, we cross out all its multiples (2i, 3i, 4i...). What remains uncrossed are the prime numbers. This ancient technique, known as the Sieve of Eratosthenes, dramatically reduces redundant calculations.

Why is this efficient? Because each composite number gets marked exactly by its prime factors, and we never need to perform division or modulo operations to check primality. We're essentially trading space (the boolean array) for time efficiency, transforming the problem from repeated primality testing to simple array marking operations.

Solution Approach

The implementation uses the Sieve of Eratosthenes algorithm with a boolean array to track prime numbers:

Step 1: Initialize the data structure

primes = [True] * n
ans = 0

We create a boolean array primes of size n where primes[i] represents whether number i is potentially prime. Initially, all values are set to True. We also initialize a counter ans to track the number of primes found.

Step 2: Iterate through potential primes

for i in range(2, n):

We start from 2 (the smallest prime) and iterate up to n-1. Numbers 0 and 1 are not prime by definition, so we skip them.

Step 3: Check and count primes

if primes[i]:
    ans += 1

If primes[i] is still True, then i hasn't been marked as composite by any smaller prime, meaning i itself is prime. We increment our counter.

Step 4: Mark multiples as non-prime

for j in range(i + i, n, i):
    primes[j] = False

For each prime i, we mark all its multiples as non-prime. Starting from 2i (which is i + i), we mark every i-th number up to n as False. The loop uses a step size of i to efficiently jump to each multiple.

Step 5: Return the result

return ans

After processing all numbers, ans contains the total count of prime numbers less than n.

The algorithm's efficiency comes from the fact that each composite number is marked only once for each of its prime factors, and we avoid redundant primality checks. The time complexity is O(n log log n) and space complexity is O(n).

Example Walkthrough

Let's walk through the algorithm with n = 12 to find all prime numbers less than 12.

Initial Setup:

• Create array primes = [True, True, True, True, True, True, True, True, True, True, True, True] (indices 0-11)
• Initialize counter ans = 0

Iteration 1: i = 2

• primes[2] = True, so 2 is prime → ans = 1
• Mark multiples of 2 as non-prime:
  • primes[4] = False (2×2)
  • primes[6] = False (2×3)
  • primes[8] = False (2×4)
  • primes[10] = False (2×5)
• Array now: [True, True, True, True, False, True, False, True, False, True, False, True]

Iteration 2: i = 3

• primes[3] = True, so 3 is prime → ans = 2
• Mark multiples of 3 as non-prime:
  • primes[6] = False (already False)
  • primes[9] = False (3×3)
• Array now: [True, True, True, True, False, True, False, True, False, False, False, True]

Iteration 3: i = 4

• primes[4] = False (marked by 2), skip marking multiples

Iteration 4: i = 5

• primes[5] = True, so 5 is prime → ans = 3
• Mark multiples of 5 as non-prime:
  • primes[10] = False (already False)
• Array now: [True, True, True, True, False, True, False, True, False, False, False, True]

Iteration 5: i = 6

• primes[6] = False (marked by 2), skip

Iteration 6: i = 7

• primes[7] = True, so 7 is prime → ans = 4
• Mark multiples of 7 as non-prime:
  • None within range (7×2 = 14 > 11)

Iterations 7-10: i = 8, 9, 10, 11

• primes[8] = False (marked by 2), skip
• primes[9] = False (marked by 3), skip
• primes[10] = False (marked by 2), skip
• primes[11] = True, so 11 is prime → ans = 5

Result: The prime numbers less than 12 are: 2, 3, 5, 7, 11 Return: ans = 5

The key insight demonstrated here is how each composite number gets eliminated by its smallest prime factor, avoiding redundant checks. For instance, 6 is marked as non-prime when processing 2 (since 6 = 2×3), and we never need to check it again when processing 3.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log log n)

The algorithm implements the Sieve of Eratosthenes. The outer loop runs from 2 to n-1, which is O(n) iterations. For each prime number i, the inner loop marks its multiples as non-prime. The number of operations for marking multiples is:

• For prime 2: n/2 operations
• For prime 3: n/3 operations
• For prime 5: n/5 operations
• And so on for each prime p: n/p operations

The total number of operations is n × (1/2 + 1/3 + 1/5 + 1/7 + ... + 1/p) where p is the largest prime less than n. This sum of reciprocals of primes up to n is approximately log log n. Therefore, the overall time complexity is O(n log log n).

Space Complexity: O(n)

The algorithm uses a boolean array primes of size n to track whether each number is prime or not. This requires O(n) space. The only other variables used are ans and loop counters i and j, which require O(1) additional space. Therefore, the total space complexity is O(n).

Common Pitfalls

1. Inefficient Multiple Marking - Starting from 2i Instead of i²

The current implementation marks multiples starting from current_num * 2, but this creates unnecessary work. When we reach a prime i, all its multiples less than i² have already been marked by smaller primes.

Why this happens: For any composite number less than i², it must have a prime factor smaller than i. For example, when processing prime 5, numbers like 10 (2×5), 15 (3×5), and 20 (4×5) have already been marked when processing primes 2 and 3.

Optimized Solution:

# Instead of:
for multiple in range(current_num * 2, n, current_num):
    is_prime[multiple] = False

# Use:
for multiple in range(current_num * current_num, n, current_num):
    is_prime[multiple] = False

2. Unnecessary Iteration - Processing All Numbers Up to n

The algorithm continues checking and marking multiples even for numbers whose square exceeds n. Once i² > n, all composite numbers less than n have already been marked.

Optimized Solution:

# Add early termination when i² > n
for current_num in range(2, n):
    if is_prime[current_num]:
        prime_count += 1
      
        # Only mark multiples if i² < n
        if current_num * current_num < n:
            for multiple in range(current_num * current_num, n, current_num):
                is_prime[multiple] = False

3. Memory Optimization for Large n

Using a full boolean array for very large values of n can consume significant memory. Each boolean typically takes 1 byte, so for n = 10^8, the array uses ~100MB.

Alternative Approaches:

• Use a bitset or bit manipulation to reduce memory by 8x
• Implement a segmented sieve for extremely large ranges
• Consider space-time tradeoffs based on constraints

4. Integer Overflow in Multiple Calculation

In some languages (though not Python), calculating current_num * current_num might cause integer overflow for large values.

Safe Implementation:

# Check if i² would exceed n before calculating
if current_num > int(n ** 0.5):
    continue  # No need to mark multiples

Complete Optimized Solution:

class Solution:
    def countPrimes(self, n: int) -> int:
        if n <= 2:
            return 0
      
        is_prime = [True] * n
        is_prime[0] = is_prime[1] = False
      
        # Only need to check up to sqrt(n)
        for i in range(2, int(n ** 0.5) + 1):
            if is_prime[i]:
                # Mark multiples starting from i², with step i
                for j in range(i * i, n, i):
                    is_prime[j] = False
      
        # Count all remaining primes
        return sum(is_prime)

This optimized version reduces unnecessary operations from O(n log log n) to a tighter bound, making it significantly faster for large inputs.