Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Count Primes

MEDIUMProblemSolveExternal Links

Description

Given an integer n, return the number of prime numbers 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, and 7 are prime, while 4, 6, 8, and 9 are not.

Your task is to count how many such prime numbers exist in the range [2, n-1].

Examples

Example 1

Input: n = 10

Output: 4

Explanation: The prime numbers strictly less than 10 are 2, 3, 5, and 7. That gives us 4 primes. Numbers like 4 (2×2), 6 (2×3), 8 (2×4), and 9 (3×3) are composite and not counted.

Example 2

Input: n = 0

Output: 0

Explanation: There are no prime numbers less than 0. The smallest prime is 2, so any n ≤ 2 yields 0.

Example 3

Input: n = 1

Output: 0

Explanation: There are no prime numbers less than 1. The number 1 itself is not considered prime by definition (it only has one divisor, not exactly two).

Example 4

Input: n = 20

Output: 8

Explanation: The primes less than 20 are 2, 3, 5, 7, 11, 13, 17, 19 — a total of 8 primes.

Constraints

  • 0 ≤ n ≤ 5 × 10^6

Editorial

Brute Force

Intuition

The most straightforward way to count primes is to check each number individually. For every number from 2 up to n-1, we ask: "Is this number prime?" If it is, we increment our counter.

To check if a single number k is prime, we try dividing it by every integer from 2 up to √k. If any of them divides k evenly, then k is composite (not prime). If none of them divide it, then k is prime.

Why only up to √k? Because if k has a factor larger than its square root, then it must also have a corresponding factor smaller than its square root. For example, if 36 is divisible by 12, it must also be divisible by 3 (since 3 × 12 = 36). So checking up to √k is sufficient.

Think of it like a security checkpoint: you examine every person (number) one by one, and for each person you run a background check (trial division). It works, but it is tediously slow when the crowd is large.

Step-by-Step Explanation

Let's trace through with n = 10:

Step 1: Initialize count = 0. We will check each number from 2 to 9 (strictly less than 10).

Step 2: Check k = 2. Try divisors from 2 to √2 ≈ 1.4. No divisors to try — 2 is prime. count = 1.

Step 3: Check k = 3. Try divisors from 2 to √3 ≈ 1.7. No divisors divide 3 — 3 is prime. count = 2.

Step 4: Check k = 4. Try divisor 2: 4 % 2 = 0. Found a divisor — 4 is NOT prime. count stays 2.

Step 5: Check k = 5. Try divisor 2: 5 % 2 = 1. No match. √5 ≈ 2.2, done. 5 is prime. count = 3.

Step 6: Check k = 6. Try divisor 2: 6 % 2 = 0. Found a divisor — 6 is NOT prime. count stays 3.

Step 7: Check k = 7. Try divisors 2 (7%2=1). √7 ≈ 2.6, done. 7 is prime. count = 4.

Step 8: Check k = 8. Try divisor 2: 8 % 2 = 0. NOT prime. count stays 4.

Step 9: Check k = 9. Try divisor 2: 9 % 2 = 1. Try divisor 3: 9 % 3 = 0. Found a divisor — NOT prime. count stays 4.

Result: count = 4. There are 4 primes less than 10.

Brute Force — Checking Each Number for Primality — Watch how we examine each number from 2 to n-1, performing trial division on each to determine if it is prime, and incrementing our count for every prime found.

Algorithm

  1. If n ≤ 2, return 0 (no primes less than 2)
  2. Initialize count = 0
  3. For each number k from 2 to n-1:
    a. Assume k is prime
    b. For each potential divisor d from 2 to √k:
    • If k % d == 0, k is not prime; break
      c. If no divisor was found, increment count
  4. Return count

Code

class Solution {
public:
    int countPrimes(int n) {
        int count = 0;
        for (int k = 2; k < n; k++) {
            bool isPrime = true;
            for (int d = 2; d * d <= k; d++) {
                if (k % d == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) count++;
        }
        return count;
    }
};
class Solution:
    def countPrimes(self, n: int) -> int:
        count = 0
        for k in range(2, n):
            is_prime = True
            d = 2
            while d * d <= k:
                if k % d == 0:
                    is_prime = False
                    break
                d += 1
            if is_prime:
                count += 1
        return count
class Solution {
    public int countPrimes(int n) {
        int count = 0;
        for (int k = 2; k < n; k++) {
            boolean isPrime = true;
            for (int d = 2; d * d <= k; d++) {
                if (k % d == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) count++;
        }
        return count;
    }
}

Complexity Analysis

Time Complexity: O(n × √n)

For each of the n numbers, we perform trial division up to its square root. The inner loop for number k runs up to √k times. Summing over all k from 2 to n gives approximately O(n × √n). With n up to 5 × 10^6, this means roughly 5×10^6 × 2236 ≈ 10^10 operations — far too slow to pass within typical time limits.

Space Complexity: O(1)

We only use a few integer variables (count, k, d, isPrime). No arrays or additional data structures are needed.

Why This Approach Is Not Efficient

The brute force checks each number independently — it does not reuse any information from previous checks. When we discover that 2 is prime, we gain the knowledge that every even number is composite. But the brute force still checks 4, 6, 8, 10, ... individually, rediscovering each time that they are divisible by 2.

Similarly, once we know 3 is prime, all multiples of 3 (6, 9, 12, 15, ...) are composite. The brute force wastes time re-verifying these facts for each number.

With n up to 5 × 10^6, the O(n√n) complexity produces about 10^10 operations, which is orders of magnitude too slow.

Key insight: instead of checking each number in isolation, what if we could eliminate all composite numbers at once? If we mark all multiples of 2 as composite, then all multiples of 3, then all multiples of 5, and so on — we only need to do work proportional to each prime, not each number. This is the idea behind the Sieve of Eratosthenes, which runs in O(n log log n) — nearly linear time.

Optimal Approach - Sieve of Eratosthenes

Intuition

The Sieve of Eratosthenes flips the problem on its head. Instead of asking "is this number prime?" for each number, it asks "which numbers are NOT prime?" and crosses them out in bulk.

Imagine writing all numbers from 2 to n-1 on a whiteboard. Start with the first number, 2 — it is prime. Now cross out every multiple of 2 (4, 6, 8, 10, ...) because they cannot be prime. Move to the next uncrossed number, which is 3 — it is prime. Cross out every multiple of 3 (9, 12, 15, ...) that is not already crossed. The next uncrossed number is 5 — cross out its multiples. Continue this process.

When you finish, every number still remaining (not crossed out) is prime. The count of remaining numbers is your answer.

Two critical optimizations make this efficient:

  1. Start marking from p²: When processing prime p, all multiples of p smaller than p² have already been marked by smaller primes. For example, when p=5, the multiples 10, 15, 20 were already crossed out when processing 2 and 3. So we start at 5²=25.
  2. Stop when p² ≥ n: Once the square of our current prime exceeds n, all remaining unmarked numbers must be prime — there are no more composites to find.

Step-by-Step Explanation

Let's trace through with n = 20 (find primes less than 20):

Step 1: Create a boolean array isPrime[0..19] initialized to true. Set isPrime[0] = false and isPrime[1] = false since 0 and 1 are not prime.

Step 2: Start with p = 2. isPrime[2] is true, so 2 is prime. Mark all multiples of 2 starting from 2² = 4: mark 4, 6, 8, 10, 12, 14, 16, 18 as false.

Step 3: Move to p = 3. isPrime[3] is true, so 3 is prime. Mark multiples of 3 starting from 3² = 9: mark 9, 12, 15, 18 as false. (12 and 18 were already marked, but that is harmless.)

Step 4: Move to p = 4. isPrime[4] is false (already marked composite). Skip it — no work needed.

Step 5: Check stopping condition: next candidate is p = 5, and 5² = 25 > 19. Since p² ≥ n, we stop the sieving process. All remaining unmarked numbers are prime.

Step 6: Count the true values in isPrime[2..19]: indices 2, 3, 5, 7, 11, 13, 17, 19 are still true.

Result: count = 8. There are 8 primes less than 20.

Sieve of Eratosthenes — Crossing Out Composites — Watch how the sieve marks multiples of each prime as composite, starting from the prime's square. Numbers that survive all rounds of crossing out are prime.

Algorithm

  1. If n ≤ 2, return 0
  2. Create a boolean array isPrime[0..n-1] initialized to true
  3. Set isPrime[0] = false and isPrime[1] = false
  4. For each p from 2 while p × p < n:
    a. If isPrime[p] is true (p is prime):
    • Mark all multiples of p as false, starting from p² up to n-1, stepping by p
  5. Count and return the number of true values in isPrime[2..n-1]

Why start from p²: Every multiple of p less than p² is of the form k × p where k < p. Since k has a prime factor ≤ k < p, that multiple was already marked when we processed that smaller prime.

Code

class Solution {
public:
    int countPrimes(int n) {
        if (n <= 2) return 0;
        
        vector<bool> isPrime(n, true);
        isPrime[0] = false;
        isPrime[1] = false;
        
        for (int p = 2; (long long)p * p < n; p++) {
            if (isPrime[p]) {
                for (int j = p * p; j < n; j += p) {
                    isPrime[j] = false;
                }
            }
        }
        
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime[i]) count++;
        }
        return count;
    }
};
class Solution:
    def countPrimes(self, n: int) -> int:
        if n <= 2:
            return 0
        
        is_prime = [True] * n
        is_prime[0] = False
        is_prime[1] = False
        
        p = 2
        while p * p < n:
            if is_prime[p]:
                for j in range(p * p, n, p):
                    is_prime[j] = False
            p += 1
        
        return sum(is_prime)
class Solution {
    public int countPrimes(int n) {
        if (n <= 2) return 0;
        
        boolean[] isPrime = new boolean[n];
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;
        
        for (int p = 2; (long) p * p < n; p++) {
            if (isPrime[p]) {
                for (int j = p * p; j < n; j += p) {
                    isPrime[j] = false;
                }
            }
        }
        
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime[i]) count++;
        }
        return count;
    }
}

Complexity Analysis

Time Complexity: O(n log log n)

The outer loop iterates over primes up to √n. For each prime p, the inner loop marks n/p multiples. The total work is:

n/2 + n/3 + n/5 + n/7 + n/11 + ... = n × (1/2 + 1/3 + 1/5 + 1/7 + ...)

The sum of reciprocals of primes up to n is approximately log(log(n)) (this is a result from analytic number theory called Mertens' theorem). Therefore, the total time is O(n log log n).

For n = 5 × 10^6, log(log(5×10^6)) ≈ 2.9, so the effective work is roughly 5×10^6 × 3 ≈ 1.5×10^7 — well within time limits.

Space Complexity: O(n)

We create a boolean array of size n to track which numbers are prime. For n = 5 × 10^6, this is about 5 MB — acceptable for most systems.