埃拉托色尼(Eratosthenes)筛法 C++代码·

埃拉托斯特尼筛法是一种用于寻找一定范围内所有质数的经典算法。它通过从2开始，逐步将每个找到的质数的所有倍数标记为非质数，直到达到给定范围的尽头。以下是简单的C++代码实现：

#include <iostream>
#include <vector>

// 判断是否为质数
bool isPrime(int num) {
    if (num <= 1)
        return false;
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0)
            return false;
    }
    return true;
}

// 埃拉托斯特尼筛法
void eratosthenesSieve(int n) {
    std::vector<bool> primes(n + 1, true); // 初始化所有数字为质数
    primes[0] = primes[1] = false;

    for (int p = 2; p * p <= n; p++) { // 只需检查到√n
        if (primes[p]) { // 如果p是质数
            for (int i = p * p; i <= n; i += p) {
                primes[i] = false; // 将p的倍数标记为非质数
            }
        }
    }

    // 输出结果
    for (int p = 2; p <= n; p++)
        if (primes[p])
            std::cout << p << " ";
}

int main() {
    int limit;
    std::cout << "请输入一个整数作为筛选范围上限: ";
    std::cin >> limit;
    eratosthenesSieve(limit);