C++ 筛法求素数 (埃拉托斯特尼筛法) - 代码示例

以下是使用筛法求解N内的素数的C++代码：\n\ncpp\n#include <iostream>\n#include <vector>\n\nusing namespace std;\n\nvoid sieveOfEratosthenes(int N) {\n // 创建一个布尔类型的数组，用于标记是否为素数\n vector<bool> isPrime(N+1, true);\n\n // 0和1不是素数，因此将其标记为false\n isPrime[0] = false;\n isPrime[1] = false;\n\n // 使用筛法将非素数标记为false\n for (int i = 2; i * i <= N; i++) {\n if (isPrime[i]) {\n for (int j = i * i; j <= N; j += i) {\n isPrime[j] = false;\n }\n }\n }\n\n // 输出所有素数\n for (int i = 2; i <= N; i++) {\n if (isPrime[i]) {\n cout << i << endl;\n }\n }\n}\n\nint main() {\n int N;\n cin >> N;\n\n sieveOfEratosthenes(N);\n\n return 0;\n}\n\n\n该代码使用了筛法（埃拉托斯特尼筛法）来求解N内的素数。首先创建一个布尔类型的数组isPrime，用于标记是否为素数。然后将数组中的0和1标记为false，因为它们不是素数。接下来，从2开始遍历数组，如果当前数字为素数，则将其倍数标记为false。最后，输出数组中为true的索引，即为素数。