[/dsa/leetcode]

204 - Count Primes

Tuesday, 15 September 2026

<medium> [problem]

Count primes below n with the Sieve of Eratosthenes, an odd-only sieve that does half the work, or Lucy_Hedgehog counting in O(n^(3/4)).

{math}{number theory}

Problem

Given an integer n, return the number of prime numbers that are strictly less than n.

Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Input: n = 0
Output: 0

Input: n = 1
Output: 0

Constraints:

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

Approach

Every prime crosses out its own multiples. Whatever is never crossed out is prime.

Start with every number marked as possibly prime. Go through i = 2, 3, 4, .... If i is still marked when we reach it, no smaller prime divides it, so it is prime, and we cross out all of its multiples.

  • Start crossing out at i * i. A smaller multiple k * i with k < i has a prime factor smaller than i, so it was already crossed out when that prime ran.
  • Stop the outer loop at i * i <= n. If i * i > n, the inner loop would start past n and do nothing. Every composite <= n has a prime factor <= √n, so everything still marked after that is prime.

Because the outer loop stops early, the primes are counted in a separate pass at the end. Only numbers strictly below n are counted.

n = 20
i = 2:  cross out 4 6 8 10 12 14 16 18 20
i = 3:  cross out 9 15            (6, 12, 18 were already gone)
i = 4:  4 * 4 = 16 <= 20, but 4 is crossed out, skip
i = 5:  5 * 5 = 25 > 20, stop
left below 20: 2 3 5 7 11 13 17 19  ->  8
class Solution {
public:
    int countPrimes(int n) {
        vector<char> p(n + 1, true);
        for(int i = 2; i * i <= n; i++) {
            if(p[i] == true) {
                for(int j = i * i; j <= n; j += i) {
                    p[j] = false;
                }
            }
        }
        int cnt = 0;
        for(int i = 2; i < n;i++){
            if(p[i] == true){
                cnt++;
            }
        }
        return cnt;
    }
};

The array is vector<char> rather than vector<bool>. vector<bool> packs each value into a single bit, which saves memory but adds bit arithmetic to every read and write. A byte per number is faster, which leaves more room

  • time: O(n log log n) - each prime p crosses out about n / p numbers, and the sum of 1 / p over primes up to n grows like log log n
  • space: O(n) - one byte per number

Odd-Only Sieve

2 is the only even prime, so the even numbers don’t need to be stored at all. Let index k stand for the odd number 2k + 1:

k:       0  1  2  3  4  5  6 ...
2k + 1:  1  3  5  7  9 11 13 ...
  • The odd numbers below n use indexes 0 to n / 2 - 1, for both odd and even n, so the array has n / 2 slots.
  • Only odd i need to cross anything out. Their odd multiples are i * i, i * i + 2i, ..., since i * i is odd and adding 2i skips the even multiples in between. Number j lives at index j / 2.
  • Index 0 is 1, which isn’t prime, so counting starts at k = 1, and cnt starts at 1 for the prime 2. For n < 3 there are no primes below n.

This does about half the work and uses half the memory of the plain sieve.

class Solution {
public:
    int countPrimes(int n) {
        if (n < 3) return 0;
        vector<char> comp(n / 2, false);
        for (int i = 3; i * i < n; i += 2) {
            if (!comp[i / 2]) {
                for (int j = i * i; j < n; j += 2 * i) {
                    comp[j / 2] = true;
                }
            }
        }
        int cnt = 1; // the prime 2
        for (int k = 1; k < n / 2; k++) {
            if (!comp[k]) cnt++;
        }
        return cnt;
    }
};
  • time: O(n log log n) — same bound, with about half the constant
  • space: O(n) — n / 2 bytes

Lucy_Hedgehog Counting

The problem asks only how many primes there are, and a sieve spends most of its time finding out which numbers are prime. Lucy_Hedgehog’s method counts them without ever listing them.

Let S(v) be how many numbers in [2, v] are still left after crossing out multiples of the primes seen so far. It starts as v - 1. Crossing out with a prime p removes numbers p * k where k >= p is still left, so

S(v) -= S(v / p) - S(p - 1)

The only v that ever come up are n / i values, and there are at most 2√n of them. The small ones are stored in lo[v] and the large ones in hi[i] = S(n / i). The full explanation, with a worked example and the reasons for the loop order, is in Lucy_Hedgehog Prime Counting.

class Solution {
public:
    int countPrimes(int n) {
        if (n < 3) return 0;
        long long m = n - 1;                      // count primes <= m
        long long r = sqrtl(m);
        while (r * r > m) r--;
        while ((r + 1) * (r + 1) <= m) r++;

        vector<long long> lo(r + 1), hi(r + 1);   // lo[v] = S(v), hi[i] = S(m / i)
        for (long long i = 1; i <= r; i++) {
            lo[i] = i - 1;
            hi[i] = m / i - 1;
        }
        for (long long p = 2; p <= r; p++) {
            if (lo[p] == lo[p - 1]) continue;     // p is not prime
            long long pc = lo[p - 1], p2 = p * p;
            long long end = min(r, m / p2);
            for (long long i = 1; i <= end; i++) {
                long long d = i * p;
                hi[i] -= (d <= r ? hi[d] : lo[m / d]) - pc;
            }
            for (long long v = r; v >= p2; v--) {
                lo[v] -= lo[v / p] - pc;
            }
        }
        return hi[1];
    }
};
  • time: O(n^(3/4)) — at n = 5 * 10^6 it runs about 50 times faster than the plain sieve above
  • space: O(√n) — two arrays of about √n entries
quantinium © 2026