L7. Count Primes in a Range L-R | Maths Playlist

This chapter explores how to efficiently solve query-based prime counting problems within a given numerical range ($L$ to $R$). Moving from a naive brute-force approach to a pre-computed prefix-sum optimization built on top of the Sieve of Eratosthenes, this note covers the step-by-step evolution of an optimal algorithmic design.

1. Problem Statement & Constraints

The core objective is to answer $Q$ independent queries, where each query provides a range $[L, R]$. For every query, we must output the total count of prime numbers existing inclusively between $L$ and $R$.

Input Parameters & Scale

• Number of Queries ($Q$): Up to $10^5$ queries.
• Range Boundaries ($L, R$): $L < R$, with $R$ scaling up to $10^6$.

2. Naive Approach & Its Limitations

The Brute-Force Strategy

In a straightforward implementation, we iterate through each query, initialize a counter to zero, and run an inner loop from $L$ to $R$. For every individual number, we invoke a prime-checking function (which takes $\mathcal{O}(\sqrt{N})$ time).

Naive Pseudo-code

def solve_naive(queries):
    for i in range(len(queries)):
        L = queries[i][0]
        R = queries[i][1]
        count = 0
        for j in range(L, R + 1):
            if isPrime(j):
                count += 1
        print(count)

Complexity Analysis

• Time Complexity: $\mathcal{O}(Q \times (R - L + 1) \times \sqrt{N})$, which easily exceeds hundreds of millions of operations under constraints like $Q = 10^5$ and $R = 10^6$. This approach results in a Time Limit Exceeded (TLE) verdict.

3. Better Approach: Sieve-Optimized Prime Checks

To remove the expensive $\mathcal{O}(\sqrt{N})$ prime check inside the query loop, we can precompute prime indicators up to the maximum possible value of $R$ ($10^6$) using the Sieve of Eratosthenes.

How the Sieve Improvement Works

1. Generate a boolean/integer array up to $10^6$ where index values mark whether a number is prime (1) or composite (0).
2. Inside the query loop, replace the heavy prime-validation function with a direct $\mathcal{O}(1)$ array lookup.

Better Approach Pseudo-code

# Precompute Sieve up to max R (10^6)
max_val = 10**6
prime_sieve = get_sieve(max_val)  # Returns array where 1 = prime, 0 = composite

def solve_better(queries):
    for query in queries:
        L, R = query[0], query[1]
        count = 0
        for j in range(L, R + 1):
            if prime_sieve[j] == 1:
                count += 1
        print(count)

Remaining Bottleneck

While we eliminated the $\sqrt{N}$ function call, we still execute an inner loop of size $(R - L + 1)$ for every single query. Multiplied by $Q = 10^5$, this remains too slow for worst-case scenarios.

4. Optimal Approach: Prefix Sum Over Sieve

To achieve an optimal $\mathcal{O}(1)$ query time, we must eliminate the inner loop entirely. We can accomplish this using a Prefix Sum Array built on top of our Sieve.

Core Mental Model & Step-by-Step Transformation

Instead of storing a binary flag ($1$ or $0$) at index $i$ in our sieve array, we modify the array to store the cumulative count of prime numbers from $1$ up to index $i$.

Example Dry Run ($N = 10$)

1. Initial Sieve Array (0/1 flags):

   CODE

   Copy

   Index:  0  1  2  3  4  5  6  7  8  9  10
   Value:  0  0  1  1  0  1  0  1  0  0   0
   

2. Accumulating Prefix Sums: We maintain a running counter = 0 and iterate from index $2$ to $10$, adding each prime flag to our running total and updating the array in place.

   • Index 2: count (0) + 1 = 1
   • Index 3: count (1) + 1 = 2
   • Index 4: count (2) + 0 = 2
   • Index 5: count (2) + 1 = 3
   • Index 6: count (3) + 0 = 3
   • Index 7: count (3) + 1 = 4
   • Index 8: count (4) + 0 = 4
   • Index 9: count (4) + 0 = 4
   • Index 10: count (4) + 0 = 4

3. Final Prefix-Sum Sieve Array:

   CODE

   Copy

   Index:  0  1  2  3  4  5  6  7  8  9  10
   Value:  0  0  1  2  2  3  3  4  4  4   4
   

   Interpretation: At index 9, the value 4 tells us instantly that there are exactly $4$ prime numbers between $1$ and $9$.

5. Range Query Formula Derivation

Once our prefix sum array is ready, answering any query $[L, R]$ requires a simple subtraction:

Why This Works

• PrefixSum[R] gives the total count of primes from $1$ up to $R$.
• PrefixSum[L - 1] gives the unwanted count of primes from $1$ up to $L - 1$.
• Subtracting the latter from the former leaves precisely the primes within $[L, R]$.

Concrete Example ($L = 3, R = 9$):

• Primes up to index $9$ (PrefixSum[9]): $4$
• Unwanted primes up to index $L-1 = 2$ (PrefixSum[2]): $1$ ($[2$ is prime$]$)
• Result: $4 - 1 = \mathbf{3}$ (Primes: $3, 5, 7$).

6. Complete Optimal Solution Implementation

Pseudo-code Implementation

def count_primes_in_ranges(queries):
    MAX_LIMIT = 10**6
    
    # Step 1: Get standard Sieve of Eratosthenes array (0/1 flags)
    prime = get_sieve(MAX_LIMIT)
    
    # Step 2: Transform Sieve into a Prefix Sum Array
    counter = 0
    for i in range(2, MAX_LIMIT + 1):
        counter += prime[i]
        prime[i] = counter  # Overwrite with cumulative count
        
    # Step 3: Answer queries in O(1) time
    results = []
    for query in queries:
        L = query[0]
        R = query[1]
        
        # Range query formula: Primes[R] - Primes[L - 1]
        ans = prime[R] - prime[L - 1]
        results.append(ans)
        
    return results

7. Comparative Strategy Analysis

Summary and Key Takeaways

• Query-Based Bottlenecks: When facing multiple queries ($Q \leq 10^5$), running inner loops bounded by range limits ($R - L$) will always result in a Time Limit Exceeded error.
• The Power of Precomputation: Pre-calculating answers beforehand shifts heavy computation to initialization phase, enabling lightning-fast responses.
• Sieve of Eratosthenes as a Black Box: The Sieve efficiently identifies all prime numbers up to $10^6$ in $\mathcal{O}(N \log \log N)$ time.
• Prefix Sum Transformation: By transforming binary sieve flags into cumulative counts, array indices directly store running totals.
• $\mathcal{O}(1)$ Query Reduction: Range prime queries simplify from an iterative search down to a single arithmetic subtraction: Prime[R] - Prime[L - 1].
• Optimal Scaling: The combined time complexity becomes $\mathcal{O}(N \log \log N + Q)$, easily accommodating large constraints without performance degradation.