筛法求小于等于n的质数，c++实现代码

筛法是一种高效求解小于等于给定数n的所有质数的方法，最著名的筛法是埃拉托斯特尼筛法（Sieve of Eratosthenes）。以下是使用C++实现的埃拉托斯特尼筛法代码示例：

#include <iostream>
#include <vector>
#include <cmath>

int main() {
    int n;
    std::cout << "请输入小于等于n的质数中的n：" << std::endl;
    std::cin >> n;

    std::vector<bool> isPrime(n + 1, true); // 初始化一个布尔型数组，标记数是否为质数，默认全部为true（质数）
    isPrime[0] = isPrime[1] = false; // 0和1不是质数，所以标记为false

    for (int i = 2; i <= std::sqrt(n); ++i) { // 从2开始筛，只需要筛到sqrt(n)，因为非质数的因子不会大于它的平方根
        if (isPrime[i]) {
            // 把当前的质数i的所有倍数标记为非质数
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    // 输出小于等于n的所有质数
    std::cout << "小于等于" << n << "的所有质数为：" << std::endl;
    for (int i = 2; i <= n; ++i) {
        if (isPrime[i]) {
            std::cout << i << " ";
        }
    }
    std::cout << std::endl;

    return 0;
}

这段代码首先创建一个布尔数组`isPrime`，并将所有小于等于n的整数标记为质数。然后，它使用两层循环来实现筛选：外层循环遍历所有数直到`sqrt(n)`，内层循环将找到的质数的所有倍数标记为非质数。最后，遍历`isPrime`数组，输出所有标记为质数的数。