c++求500以内所有的素数

埃拉托色尼筛法（Sieve of Eratosthenes）是一种高效的算法，用于在一定范围内找出所有素数。它的基本思想是：从2开始，标记所有2的倍数为非素数，然后找到下一个未标记的数字，标记它的倍数为非素数，如此反复，直到处理完所有小于等于指定范围内的数字。

具体步骤如下：

1. 初始化列表：创建一个从2到指定范围的所有整数列表。假设列表中的每个数都是素数。

2. 从最小素数开始标记：从第一个素数2开始，标记所有2的倍数为非素数。

3. 找到下一个未标记的数：即下一个素数，并标记它的所有倍数为非素数。

4. 重复步骤2和3：直到遍历到指定范围的平方根为止。因为更大的数如果不是素数，早已被标记。

5. 提取所有素数：所有未被标记的数即为素数。

这个算法的时间复杂度为 $O(n\log \log n)$，适合处理较大范围内的素数求解。

以下是用C++实现埃拉托色尼筛法求500以内素数的代码示例：

#include <iostream>
#include <vector>

void sieveOfEratosthenes(int limit) {
    std::vector<bool> isPrime(limit + 1, true);
    isPrime[0] = isPrime[1] = false;  // 0和1不是素数

    for (int i = 2; i * i <= limit; ++i) {
        if (isPrime[i]) {
            for (int j = i * i; j <= limit; j += i) {
                isPrime[j] = false;  // 标记i的倍数为非素数
            }
        }
    }

    for (int i = 2; i <= limit; ++i) {
        if (isPrime[i]) {
            std::cout << i << " ";
        }
    }
}

int main() {
    int limit = 500;
    sieveOfEratosthenes(limit);
    return 0;
}

代码解析：

1. 初始化isPrime向量： 代码首先创建一个布尔向量isPrime，大小为limit + 1，所有值初始为true。这个向量用于标记数字是否为素数。

2. 处理0和1： 数组的第0和1位设为false，因为0和1不是素数。

3. 主循环： 从2开始，逐个检查数字，如果某数字为素数（isPrime[i]为true），则将其倍数标记为非素数。

4. 输出素数： 最后，遍历整个向量，输出所有标记为true的数字，这些即为素数。

这个程序在运行时会输出500以内的所有素数。

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499
Process returned 0 (0x0)   execution time : 0.018 s