用c++找出1到n的素数的个数

在C++中，找出从1到n的素数个数可以采用埃拉托斯特尼筛法（Sieve of Eratosthenes）算法。这个算法的基本思想是从2开始，将所有2的倍数标记为合数，然后找到下一个未被标记的数3，将它的所有倍数标记为合数，如此循环直到sqrt(n)。最后，未被标记的数就是素数。
以下是简单的C++代码示例：
#include <iostream>
#include <vector>

using namespace std;

int countPrimes(int n) {
vector<bool> isPrime(n+1, true); // 真数组初始化为素数
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; // 将i的倍数标记为合数
}
}
}

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

return primeCount;
}

int main() {
int n;
cout << "Enter a number: ";
cin >> n;
cout << "The number of primes from 1 to " << n << " is: " << countPrimes(n);
return 0;
}
登录后复制
在这个程序中，countPrimes()函数返回1到n之间的素数个数。用户可以通过输入值n来获取结果。