Count Primes

Problem in Plain English

Count the prime numbers strictly below n. A prime is an integer greater than one whose only positive divisors are one and itself.

Problem Statement

Given a nonnegative integer n, return the number of primes strictly less than n. A prime has exactly two positive divisors: 1 and itself.

The upper endpoint is excluded: for n = 2, the answer is 0; for n = 3, the answer is 1 because only 2 qualifies.

Constraints

0 <= n <= 5 * 10^6.

Examples

Example 1

Input: n = 10
Output: 4

Exactly 2, 3, 5 and 7 are prime below 10. The values 4, 6, 8 and 9 have smaller divisors, and 1 is not prime.

Example 2

Input: n = 0
Output: 0

There are no positive prime candidates below zero; return before allocating a sieve.

Example 3

Input: n = 1
Output: 0

The only nonnegative candidate below 1 is 0, which is not prime.

Example 4

Input: n = 3
Output: 1

The prime 2 is included, but 3 itself is excluded. This distinguishes strict from inclusive counting.

Example 5

Input: n = 50
Output: 15

The primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43 and 47. Marking 49 when processing 7 is essential.

Intuition

For n = 10, the candidates are 2 through 9. Testing divisors identifies 2, 3, 5, 7 as prime. But each composite has a smaller prime factor: 6 can be rejected when processing 2, without testing it separately. A sieve records these rejections for all candidates together. When 3 is reached, its smaller multiples have already been handled by 2, so its first new multiple is 9.

Approaches

Trial Division

Solution Details

Reveal Trial Division: intuition, complexity, and code

Intuition

Test each candidate independently by searching for a divisor no larger than its square root. A factor larger than the square root must pair with a smaller factor, so divisors beyond that point add no information.

Step-by-Step Logic

Initialize count to 0 and inspect x from 2 up to, but not including, n. Example 1 considers 2 through 9.
For each x, try d from 2 while d*d <= x. If x % d is zero, stop and reject x. Values 2 and 3 need no divisor checks and raise count to 2.
At x = 4, divisor 2 rejects it. At x = 5, divisor 2 fails and the next square is too large, so count becomes 3.
Reject 6 using 2, accept 7 after checking 2, and reject 8 using 2. Count is now 4.
For 9, divisor 2 fails but divisor 3 succeeds; do not count it. Return 4.

Why It Works

For each candidate x greater than one, a found divisor proves it composite. If x were composite with no divisor at most its square root, both factors of every factorization would be larger than the square root and their product would exceed x, a contradiction. Therefore accepting after all d with d*d <= x fail accepts exactly the primes. The outer loop visits every integer from 2 through n-1 exactly once, so counting those accepted yields precisely the requested total.

Dry Run

Trial Division: variable states at each step
x	Divisors tested	Decision	Count
2	none	prime	1
3	none	prime	2
4	2 divides	composite	2
5	2 fails	prime	3
6	2 divides	composite	3
7	2 fails	prime	4
8	2 divides	composite	4
9	2 fails; 3 divides	composite	4
return	all candidates checked	4	4

Complexity Analysis

Time Complexity

O(n\sqrt{n})

Space Complexity

O(1)

There are at most n candidates and at most sqrt(n) divisor attempts per candidate, giving this upper bound, not a claim that every candidate uses every attempt. Early rejection reduces actual work. Only counters and a boolean are stored. For n below 3 the work is constant. This teaching baseline is slow at the maximum bound; divisor squares stay within the Java int and exact JavaScript integer ranges.

Code

Solution.java

1class Solution {2    public int countPrimes(int n) {3        int count = 0;4        for (int x = 2; x < n; x++) {5            boolean prime = true;6            for (int d = 2; d * d <= x; d++) {7                if (x % d == 0) { prime = false; break; }8            }9            if (prime) count++;10        }11        return count;12    }13}

Hints

Hint 1

A composite has a factor at most its square root.

Hint 2

Instead of testing each number, record the multiples of each discovered prime.

Hint 3

Start crossing out multiples at p*p, and never include position n in the final count.

Edge Cases

For n = 0, 1 or 2, return 0 without treating 1 as prime.
When n itself is prime, it is excluded; countPrimes(3) is 1.
A square just below the bound must be marked: 49 is composite when n = 50.
The maximum bound needs linear flag storage; do not build lists of divisors or candidate strings.

Common Mistakes and Interview Tips

Marking from p rather than p*p crosses out the prime itself.
Using p*p < x in trial division misses perfect squares; use <= there.
Including n changes the strictly-less-than problem into inclusive counting.
Processing every candidate as a marking prime wastes work; skip flagged composites.

Key Takeaway

When many queries share a bounded integer domain, preprocess facts across that domain instead of repeating a search for each value. A prime sieve discovers one factor and eliminates all its relevant multiples.