牛客234957题解：用埃拉托斯特尼筛法解决质数的计数

4天前牛客题解68

一、问题分析

这道题目要求我们统计小于给定正整数n的所有质数的数量。质数是指大于1的自然数，除了1和它本身外没有其他因数。题目给定的数据范围是1≤n≤10^5，我们需要一个高效的算法来解决这个问题。

二、算法选择

最直观的方法是逐个检查每个数是否为质数，但这种方法的时间复杂度较高(O(n√n))。更高效的算法是埃拉托斯特尼筛法(Sieve of Eratosthenes)，其时间复杂度为O(n log log n)，非常适合本题的数据范围。

三、埃拉托斯特尼筛法原理

1.创建一个大小为n的布尔数组，初始值全为true

2.从第一个质数2开始，将其倍数标记为非质数

3.对后续未被标记的数重复上述过程

4.最后统计数组中仍为true的元素数量

四、完整代码

#include <iostream>
#include <vector>
using namespace std;

int countPrimes(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) {
        if (isPrime[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;
}

int main() {
    int n;
    cin >> n;
    cout << countPrimes(n) << endl;
    return 0;
}