c++ 统计1-100之间的素数个数

在 C++ 中，统计 1 到 100 之间的素数个数可以采用一种常见的算法，即埃拉托斯特尼筛法（Sieve of Eratosthenes）。这是一种用于找出一定范围内所有质数的有效方法。以下是简单的步骤：

创建一个布尔数组 isPrime[101]，初始化所有元素为 true，表示从 2 到 100 的数字都是潜在的素数。
遍历数组，从第一个质数 2 开始：
如果当前数 i 是质数（isPrime[i] 为 true），将它的所有倍数标记为非素数（将 isPrime[j * i] 设为 false，其中 j 从 2 到 i / j）。

当遍历结束后，isPrime 数组中为 true 的元素就是素数，它们对应的索引加一就得到了素数的数量。

下面是对应的 C++ 代码示例：
#include <iostream>
using namespace std;

void countPrimes(int n) {
bool isPrime[n + 1];
memset(isPrime, true, sizeof(isPrime));
isPrime[0] = isPrime[1] = false; // 0 和 1 不是素数

for (int i = 2; i * i <= n; ++i) { // 只需检查到根号n
if (isPrime[i]) {
for (int j = i * i; j <= n; j += i)
isPrime[j] = false;
}
}

int primeCount = 0;
for (int i = 2; i <= n; ++i)
if (isPrime[i])
primeCount++;

cout << "1到" << n << "之间有 " << primeCount << " 个素数。\n";
}

int main() {
countPrimes(100);
return 0;
}
登录后复制
运行此程序后，它会输出 1 到 100 之间素数的个数。