牛客234957题：埃拉托斯特尼筛法高效求解质数计数问题

一、题目解读

牛客234957题要求计算给定整数n以内（不含n）的质数数量。质数即大于1且只能被1和自身整除的自然数。题目考察高效的质数筛法，需在保证正确性的基础上优化时间复杂度，避免暴力枚举导致的超时问题。

二、解题思路

采用经典的埃拉托斯特尼筛法解决该问题。核心思路如下：

1. 标记合数：从2开始，将每个质数的倍数全部标记为合数，剩余未标记的数即为质数。

2. 优化筛法边界。

3. 时间复杂度优化：通过避免重复标记，将复杂度降至O(nloglogn)，远优于朴素试除法。

该解法简洁高效，是处理质数相关问题的基础算法之一。

三、解题步骤

1. 初始化标记数组：创建长度为n的布尔数组isPrime，默认所有数标记为质数（true），特殊处理0和1（非质数，置为false）。

2. 执行筛法：从2开始遍历，若当前数i为质数（即isPrime[i] == true），则将其所有倍数（从i2开始，步长为i）标记为合数（置为false）。

3. 统计质数数量：遍历数组，累计isPrime[i] == true的个数（i从2到n-1）。

通过以上步骤，利用筛法“由小到大逐步排除合数”的特性，高效获取质数集合。

四、代码与注释

class Solution {
public:
    int primesCount(int n) {
        if (n <= 2) return 0; // 小于2的数没有质数
        vector<bool> isPrime(n, true); // 初始化所有数为质数
        isPrime[0] = isPrime[1] = false; // 0和1不是质数

        // 埃拉托斯特尼筛法核心
        for (int i = 2; i * i < n; ++i) { // 遍历到√n即可
            if (isPrime[i]) { // 若i是质数
                // 将i的倍数标记为非质数
                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;
    }
};

五、总结

本解法通过埃拉托斯特尼筛法实现了质数计数的优化求解，其核心在于“通过质数的倍数排除合数”，并通过边界优化减少循环次数。该算法不仅是解决质数问题的经典方法，也为更高效的线性筛法（如欧拉筛）奠定了基础。在实际应用中，对于中小规模范围内的质数统计场景，埃氏筛法具有极高的实用价值。