给定一个正整数n(n>2),统计所有的小于或者等于n的素数的个数。 关于输入 有一行,整数n 关于输出 只有一行,输出小于等于n的素数的个数。
时间: 2024-10-25 18:15:34 浏览: 43
要计算小于或等于给定正整数n的素数个数,我们可以使用一种高效的算法,即埃拉托斯特尼筛法(Sieve of Eratosthenes)。这个算法逐个标记数字,排除那些不是素数的,最后剩下的就是素数。
以下是一个简单的C++代码实现:
```cpp
#include <iostream>
#include <vector>
int countPrimes(int n) {
std::vector<bool> isPrime(n+1, true); // 初始假设所有数字都是素数
isPrime[0] = false; // 0和1不是素数
isPrime[1] = false;
for (int i = 2; i * i <= n; ++i) { // 遍历到 sqrt(n),因为大于该值的因子肯定已经在之前被处理过了
if (isPrime[i]) { // 如果i是素数
for (int j = i * i; j <= n; j += i) { // 将 i 的倍数标记为非素数
isPrime[j] = false;
}
}
}
int primeCount = 0;
for (int i = 2; i <= n; ++i) {
if (isPrime[i]) {
++primeCount;
}
}
return primeCount;
}
int main() {
int n;
std::cout << "Enter a positive integer (n > 2): ";
std::cin >> n;
int result = countPrimes(n);
std::cout << "The number of primes less than or equal to " << n << " is: " << result << std::endl;
return 0;
}
```
在这个代码中,`countPrimes` 函数首先创建一个布尔数组 `isPrime`,然后通过循环遍历从2开始到√n,对于每个素数i,将其所有的倍数标记为非素数。最后,计数并返回小于或等于n的素数数量。
阅读全文