☕ DSA Java Articles

Topics › Bit Manipulation › Advanced Maths

Count primes in range L to R

Hard TUF ID 651 A2Z

Java source ↗ Edit this article ↗

Problem

You are given two integers L and R. Return how many prime numbers lie in the inclusive range [L, R]. In the full version of the problem you are given Q such ranges and must answer all of them, which is what makes it “hard”: the intended solution does all the heavy lifting once and then answers each query in constant time.

Constraints: 0 ≤ L ≤ R ≤ 10^6, 1 ≤ Q ≤ 10^5. Remember that 0 and 1 are not prime and 2 is the only even prime.

Example 1

L = 1, R = 10
answer = 4           // 2, 3, 5, 7

Example 2

L = 10, R = 20
answer = 4           // 11, 13, 17, 19

Example 3

queries = [[1, 10], [10, 20], [1, 100], [50, 60]]
answer = [4, 4, 25, 2]        // 53 and 59 are the primes in [50, 60]

Approach 1: Brute force

Intuition. Test every number in the range for primality with trial division: x is prime if x ≥ 2 and no d in [2, sqrt(x)] divides it. It is correct and simple, and for a single short range it is perfectly adequate. It does not scale: each number costs up to sqrt(R) divisions and nothing is shared between numbers, let alone between queries.

Algorithm.

  1. Set count = 0.
  2. For x from L to R, if isPrime(x), increment count.
  3. Return count.
static int bruteForce(int l, int r) {
    int count = 0;
    for (int x = l; x <= r; x++) {
        if (isPrime(x)) count++;
    }
    return count;
}

static boolean isPrime(int x) {
    if (x < 2) return false;
    for (long d = 2; d * d <= x; d++) {
        if (x % d == 0) return false;
    }
    return true;
}

Complexity. Time O((R - L + 1) × sqrt(R)) per query; with Q queries that becomes O(Q × (R - L + 1) × sqrt(R)). For R = 10^6 a single full range is already about 10^8 operations in the worst case, and 10^5 queries are out of the question. Space O(1).

Approach 2: Better, sieve up to R then count

Intuition. Trial division asks, for each number, “which small numbers divide me?” The sieve of Eratosthenes turns the question around: for each small prime p, “which numbers do I divide?” Those are simply p × p, p × p + p, p × p + 2p, ..., reachable by addition with no division at all. Start with every number unmarked, and for each p from 2 that is still unmarked (hence prime), mark all its multiples from p × p onward as composite. When the outer loop passes sqrt(R), every composite up to R has been marked, because every composite has a prime factor at most its square root. Then counting primes in [L, R] is a scan over a boolean array.

Why start marking at p × p rather than 2p? Any smaller multiple k × p with k < p has a prime factor smaller than p and was marked earlier, when that smaller prime was processed.

Algorithm.

  1. Build composite[0..R] with the sieve, marking 0 and 1 as not prime.
  2. Count the indices x in [max(L, 2), R] with composite[x] == false.
static int better(int l, int r) {
    boolean[] composite = sieve(r);
    int count = 0;
    for (int x = Math.max(l, 2); x <= r; x++) {
        if (!composite[x]) count++;
    }
    return count;
}

static boolean[] sieve(int n) {
    boolean[] composite = new boolean[Math.max(n, 1) + 1];
    composite[0] = true;
    composite[1] = true;
    for (long p = 2; p * p <= n; p++) {
        if (!composite[(int) p]) {
            for (long multiple = p * p; multiple <= n; multiple += p) composite[(int) multiple] = true;
        }
    }
    return composite;
}

Complexity. Time O(R log log R) for the sieve plus O(R - L + 1) for the count. The log log comes from summing R / p over the primes p ≤ sqrt(R), which is R × (1/2 + 1/3 + 1/5 + ...), a famously slow-growing sum. Space O(R) for the boolean array.

For one query this is already a huge win over trial division. For Q queries it still rebuilds the sieve and rescans the range every time, so the per-query cost is O(R), not constant.

Approach 3: Optimal, one sieve plus prefix counts

Intuition. Two observations make queries free. First, the sieve does not depend on the query, only on the largest R involved, so build it once. Second, “how many primes in [L, R]” is a range-sum question over the indicator array isPrime[x], and range sums are answered in constant time with prefix sums: let primesUpTo[x] be the number of primes in [0, x]; then the count in [L, R] is primesUpTo[R] - primesUpTo[L - 1], with the second term taken as 0 when L = 0.

Algorithm.

  1. Find maxR, the largest right endpoint among the queries, and sieve up to it.
  2. Build primesUpTo[x] = primesUpTo[x - 1] + (1 if x is prime else 0) for x from 1 to maxR, with primesUpTo[0] = 0.
  3. For each query (l, r), output primesUpTo[r] - (l > 0 ? primesUpTo[l - 1] : 0).
static int[] optimal(int[][] queries) {
    int maxR = 0;
    for (int[] q : queries) maxR = Math.max(maxR, q[1]);
    boolean[] composite = sieve(maxR);
    int[] primesUpTo = new int[maxR + 1];              // primesUpTo[x] = number of primes in [0, x]
    for (int x = 1; x <= maxR; x++) primesUpTo[x] = primesUpTo[x - 1] + (composite[x] ? 0 : 1);
    int[] answers = new int[queries.length];
    for (int i = 0; i < queries.length; i++) {
        int l = queries[i][0], r = queries[i][1];
        answers[i] = primesUpTo[r] - (l > 0 ? primesUpTo[l - 1] : 0);
    }
    return answers;
}

Dry run with maxR = 20. The sieve marks 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20 (multiples of 2 from 4, of 3 from 9; 5 × 5 = 25 > 20 ends the outer loop). The prefix table:

x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
prime? - - y y - y - y - - - y - y - - - y - y -
primesUpTo 0 0 1 2 2 3 3 4 4 4 4 5 5 6 6 6 6 7 7 8 8

Query [10, 20]: primesUpTo[20] - primesUpTo[9] = 8 - 4 = 4. Query [1, 10]: primesUpTo[10] - primesUpTo[0] = 4 - 0 = 4.

Complexity. Time O(N log log N + N + Q) where N = maxR: sieve, prefix pass, then O(1) per query. Space O(N) for the two arrays.

Edge cases and pitfalls