AlgoMaster Logo

Count Primes

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We need to count how many prime numbers exist below a given number n. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. So for n = 10, the primes less than 10 are 2, 3, 5, and 7, giving us a count of 4.

Determining whether a single number is prime is straightforward. The difficulty is doing it for every number from 2 to n - 1 when n can be as large as 5 million. Checking each number independently repeats the same divisibility work over and over. The structure of prime numbers allows a faster method that eliminates composites in bulk.

Key Constraints:

  • 0 <= n <= 5 * 10^6 → Trial division on each number independently takes O(n * sqrt(n)), which is roughly 11 billion operations at the upper bound. The approach has to be closer to O(n log log n).
  • n can be 0 or 1 → The answer is 0 since there are no primes below 2. The solution must handle these without indexing into an empty array.

Approach 1: Brute Force (Trial Division)

Intuition

For each number from 2 to n - 1, check whether it is prime by testing divisibility. To determine if a single number k is prime, try dividing it by every integer from 2 up to sqrt(k). If none of them divide k evenly, then k is prime.

Testing up to sqrt(k) suffices: if k = a * b and both a and b were greater than sqrt(k), then a * b > k, a contradiction. So every composite k has at least one factor at or below sqrt(k).

Algorithm

  1. If n is less than or equal to 2, return 0 (no primes below 2).
  2. Initialize a counter count = 0.
  3. For each number i from 2 to n - 1:
    • Check if i is prime by testing divisibility from 2 to sqrt(i).
    • If no divisor is found, increment count.
  4. Return count.

Example Walkthrough

1n=10: check each number from 2 to 9, count=0
0
2
i
1
3
2
4
3
5
4
6
5
7
6
8
7
9
1/6

Code

Trial division tests 4, 6, 8, and every other even number against 2 one at a time. The next approach inverts the direction: each prime, once found, eliminates all of its multiples in a single pass.

Approach 2: Sieve of Eratosthenes

Intuition

The Sieve of Eratosthenes reverses the question. Instead of asking "is this number prime?" for each number, we start by assuming every number is prime and then systematically cross out the ones that are not.

If p is a prime, then every multiple of p (2p, 3p, 4p, ...) is composite, so each prime we find lets us mark a whole family of composites in one pass. Sieving with every prime up to sqrt(n) is enough: any composite below n has a prime factor at most sqrt(n), so none survives.

There is one more optimization: when marking multiples of a prime p, we can start from p * p rather than 2 * p, because all smaller multiples of p have already been marked by smaller primes.

Algorithm

  1. If n is less than or equal to 2, return 0.
  2. Create a boolean array isPrime of size n, initialized to true.
  3. Set isPrime[0] and isPrime[1] to false (0 and 1 are not prime).
  4. For each number p starting at 2, while p * p < n:
    • If isPrime[p] is true, mark all multiples of p starting from p * p as false.
  5. Count and return the number of true values in the array.

Example Walkthrough

1n=20: initialize isPrime[0]=F, isPrime[1]=F, rest=T
0
F
1
F
2
T
p
3
T
4
T
5
T
6
T
7
T
8
T
9
T
10
T
11
T
12
T
13
T
14
T
15
T
16
T
17
T
18
T
19
T
1/5

Code