如何用筛法编写求素数的代码？

筛法是一种高效的查找素数的方法，最常见的是埃拉托斯特尼筛法（Sieve of Eratosthenes）。这个算法的基本思想是从2开始，将每个素数的倍数标记为合数，直到达到某个范围内的最大值。下面是使用C++实现的一个简单版本：

#include <iostream>
#include <vector>

// 使用布尔数组标记是否为素数
std::vector<bool> sieve(int n) {
    std::vector<bool> is_prime(n+1, true); // 假设所有数字都是质数
    is_prime[0] = false; // 0和1不是素数
    is_prime[1] = false;

    for (int i = 2; i * i <= n; ++i) { // 只需检查到 sqrt(n)
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = false; // 标记 i 的倍数为合数
            }
        }
    }

    return is_prime;
}

int main() {
    int limit;
    std::cout << "Enter the upper limit for finding primes: ";
    std::cin >> limit;

    std::vector<bool> primes = sieve(limit);
    for (int i = 2; i <= limit; ++i) {
        if (primes[i]) {
            std::cout << i << " is a prime number.\n";
        }
    }

    return 0;
}

在这个代码中，我们首先创建一个布尔数组`is_prime`，其中索引表示数字，初始时都假设为素数。然后从2开始遍历，如果当前数字是素数，则将其倍数标记为合数。最后，输出那些仍然标记为素数的数字。