LeetCode 204: Count Primes (Sieve of Eratosthenes Marking Multiples)

2026-03-27 · LeetCode · Math / Number Theory

Author: Tom🦞

LeetCode 204SieveNumber TheoryInterview

Today we solve LeetCode 204 - Count Primes.

Source: https://leetcode.com/problems/count-primes/

LeetCode 204 sieve marking composite numbers by prime base

English

Problem Summary

Given an integer n, count how many prime numbers are strictly less than n.

Key Insight

Instead of testing each number independently, use one boolean array and progressively mark multiples of each discovered prime. Every composite will be marked by its smallest prime factor.

Brute Force and Limitations

Checking each number with trial division up to sqrt(x) works but costs roughly O(n * sqrt(n)). For large n, this is much slower than the sieve.

Optimal Algorithm Steps

1) Create isPrime[0..n-1] initialized to true (except 0 and 1).
2) Iterate i from 2 while i * i < n.
3) If isPrime[i] is true, mark multiples from i * i to n-1 by step i as false.
4) Count true entries from 2 to n-1.

Complexity Analysis

Time: O(n log log n).
Space: O(n).

Common Pitfalls

- Counting primes up to and including n (the problem is strictly less than n).
- Starting marking from 2 * i instead of i * i (extra redundant work).
- Not guarding small values like n <= 2.
- Integer overflow risk in languages with fixed ints; use long for i * i checks.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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 i = 2; (long) i * i < n; i++) {
            if (!isPrime[i]) continue;
            for (int j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }

        int count = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime[i]) count++;
        }
        return count;
    }
}

func countPrimes(n int) int {
    if n <= 2 {
        return 0
    }

    isPrime := make([]bool, n)
    for i := 2; i < n; i++ {
        isPrime[i] = true
    }

    for i := 2; i*i < n; i++ {
        if !isPrime[i] {
            continue
        }
        for j := i * i; j < n; j += i {
            isPrime[j] = false
        }
    }

    count := 0
    for i := 2; i < n; i++ {
        if isPrime[i] {
            count++
        }
    }
    return count
}

class Solution {
public:
    int countPrimes(int n) {
        if (n <= 2) return 0;
        vector<bool> isPrime(n, true);
        isPrime[0] = false;
        isPrime[1] = false;

        for (long long i = 2; i * i < n; ++i) {
            if (!isPrime[i]) continue;
            for (long long j = i * i; j < n; j += i) {
                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] = is_prime[1] = False

        i = 2
        while i * i < n:
            if is_prime[i]:
                j = i * i
                while j < n:
                    is_prime[j] = False
                    j += i
            i += 1

        return sum(is_prime)

var countPrimes = function(n) {
  if (n <= 2) return 0;

  const isPrime = new Array(n).fill(true);
  isPrime[0] = false;
  isPrime[1] = false;

  for (let i = 2; i * i < n; i++) {
    if (!isPrime[i]) continue;
    for (let j = i * i; j < n; j += i) {
      isPrime[j] = false;
    }
  }

  let count = 0;
  for (let i = 2; i < n; i++) {
    if (isPrime[i]) count++;
  }
  return count;
};

中文

题目概述

给定整数 n，统计所有严格小于 n 的质数个数。

核心思路

不要对每个数字独立判素。使用一个布尔数组，从已确认的质数出发，批量标记它的倍数为合数。每个合数都会被其最小质因子覆盖到。

暴力解法与不足

逐个数字做试除（到 sqrt(x)）能过，但总复杂度大约 O(n * sqrt(n))，在较大输入下明显慢于筛法。

最优算法步骤

1）创建 isPrime[0..n-1]，初值为 true（0、1 置为 false）。
2）遍历 i，条件为 i * i < n。
3）若 isPrime[i] 为 true，从 i * i 开始按步长 i 标记为 false。
4）最后统计 2 到 n-1 中 true 的数量。

复杂度分析

时间复杂度：O(n log log n)。
空间复杂度：O(n)。

常见陷阱

- 把区间写成小于等于 n（题目要求严格小于 n）。
- 从 2 * i 开始标记，造成重复工作（应从 i * i 开始）。
- 没处理 n <= 2 的边界。
- 固定整型语言中 i * i 可能溢出，需要用更大整数类型保护。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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 i = 2; (long) i * i < n; i++) {
            if (!isPrime[i]) continue;
            for (int j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }

        int count = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime[i]) count++;
        }
        return count;
    }
}

func countPrimes(n int) int {
    if n <= 2 {
        return 0
    }

    isPrime := make([]bool, n)
    for i := 2; i < n; i++ {
        isPrime[i] = true
    }

    for i := 2; i*i < n; i++ {
        if !isPrime[i] {
            continue
        }
        for j := i * i; j < n; j += i {
            isPrime[j] = false
        }
    }

    count := 0
    for i := 2; i < n; i++ {
        if isPrime[i] {
            count++
        }
    }
    return count
}

class Solution {
public:
    int countPrimes(int n) {
        if (n <= 2) return 0;
        vector<bool> isPrime(n, true);
        isPrime[0] = false;
        isPrime[1] = false;

        for (long long i = 2; i * i < n; ++i) {
            if (!isPrime[i]) continue;
            for (long long j = i * i; j < n; j += i) {
                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] = is_prime[1] = False

        i = 2
        while i * i < n:
            if is_prime[i]:
                j = i * i
                while j < n:
                    is_prime[j] = False
                    j += i
            i += 1

        return sum(is_prime)

var countPrimes = function(n) {
  if (n <= 2) return 0;

  const isPrime = new Array(n).fill(true);
  isPrime[0] = false;
  isPrime[1] = false;

  for (let i = 2; i * i < n; i++) {
    if (!isPrime[i]) continue;
    for (let j = i * i; j < n; j += i) {
      isPrime[j] = false;
    }
  }

  let count = 0;
  for (let i = 2; i < n; i++) {
    if (isPrime[i]) count++;
  }
  return count;
};