求出n以内的素数c++
时间: 2025-02-09 22:11:05 浏览: 116
### C++ 实现求解 n 以内素数
为了计算给定范围内所有的素数,在C++中可以通过优化后的算法来提高效率。下面展示了一种基于埃拉托斯特尼筛法的思想,该方法相比简单的双重循环更加高效。
#### 使用埃拉托斯特尼筛法求解 n 以内的所有素数
埃拉托斯特尼筛法是一种古老的用于寻找小于自然数n的所有素数的方法。其基本原理是从最小的素数2开始,将它的倍数都标记成合数;接着找到下一个未被标记过的数字作为新的素数,并重复上述过程直到遍历结束。
以下是采用此思想编写的C++代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
void findPrimes(int n) {
vector<bool> prime(n + 1, true);
for (int p = 2; p * p <= n; ++p) {
if (prime[p]) {
for (int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
cout << "Prime numbers up to " << n << ": ";
for (int p = 2; p <= n; ++p)
if (prime[p])
cout << p << ' ';
}
int main() {
int num;
cout << "Enter a number: ";
cin >> num;
findPrimes(num);
return 0;
}
```
这段代码首先创建了一个布尔类型的向量`prime[]`用来记录各个数值是否为素数,默认初始化为true表示假设所有都是素数。之后通过迭代的方式逐步排除掉那些已经被确认是非素数的位置,最终输出剩余下来的即为所求区间内全部素数[^3]。
阅读全文
相关推荐
















