LeetCode 204. 计数质数

Categories:

题目描述
思路分析
1. 解法一：埃氏筛（推荐）
相似题目

题目描述

✅ 204. 计数质数

思路分析

解法一：埃氏筛（推荐）

核心思路：

创建 isPrime 数组，初始认为 2..n-1 都是质数。

从 2 开始筛掉其倍数，i * i < n 即可。

最终统计为 true 的数量。

复杂度分析：

时间复杂度：O(n log log n)，其中 n 表示上界。

空间复杂度：O(n)，使用标记数组。

// 埃氏筛统计质数
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; 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
}

相似题目

题目	难度	考察点
263. 丑数	简单	数论
264. 丑数 II	中等	数论
866. 回文素数	中等	数论
762. 二进制表示中质数个计算置位	简单	数论
367. 有效的完全平方数	简单	数学
509. 斐波那契数	简单	数学

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/62404477