用C++判断101-200之内的素数
时间: 2024-10-01 22:08:49 浏览: 31
蓝桥杯c++-蓝桥杯竞赛练习之算法提高题素数判断.zip
在C++中,我们可以使用一种称为“埃拉托斯特尼筛法”(Sieve of Eratosthenes)的经典算法来找出101到200之间的素数。这是一种通过排除能被已知素数整除的所有数的方式来寻找素数的方法。下面是基本的步骤:
1. 创建一个布尔数组`isPrime`,长度从2开始到给定范围的上限(这里是200),并初始化所有元素为`true`。因为2是最小的质数,我们把它标记为素数。
2. 遍历数组,从第一个素数2开始。对于每个素数`p`,将它的倍数(除了它本身)都设置为非素数,即`isPrime[p * i] = false`,这里`i`从2开始直到`sqrt(p)`。
3. 遍历数组`isPrime`,如果某个位置`i`对应的值为`true`,则`i`是一个素数。
以下是C++代码实现这一过程:
```cpp
#include <iostream>
#include <vector>
#include <cmath>
bool isPrime(int num) {
if (num <= 1)
return false;
if (num == 2 || num == 3)
return true;
if (num % 2 == 0 || num % 3 == 0)
return false;
for (int i = 5; i * i <= num; i += 6) {
if (num % i == 0 || num % (i + 2) == 0)
return false;
}
return true;
}
void printPrimesInRange(int start, int end) {
std::vector<bool> isPrime(end + 1, true); // 空白区域默认为素数假设
isPrime[0] = isPrime[1] = false; // 0和1不是素数
for (int p = 2; p * p <= end; ++p) {
if (isPrime[p]) {
for (int i = p * p; i <= end; i += p) {
isPrime[i] = false; // 标记p的倍数为非素数
}
}
}
for (int num = start; num <= end; ++num) {
if (isPrime[num])
std::cout << num << " ";
}
}
int main() {
int start = 101, end = 200;
printPrimesInRange(start, end);
return 0;
}
```
当你运行这段程序,它会打印出101到200之间所有的素数。
阅读全文