极客教程C++程序 寻找给定区间内的质数
给定两个数字a和b作为区间范围，任务是在这个区间内找出所有的质数。
例子：
输入： a = 1，b = 10
输出： 2，3，5，7
输入： a = 10，b = 20
输出： 11，13，17，19
在下面的程序中，区间数字作为输入存储在变量’a’和’b’中。然后使用for循环遍历a和b之间的数字。对于for循环中的每个数字，都会检查该数字是否为质数。如果是质数，则打印该数字。然后继续检查循环中的下一个数字，直到所有数字都被检查完成。
程序：
// C++ program to find the
// prime numbers between a
// given interval
#include <bits/stdc++.h>
using namespace std;
// Driver code
int main()
{
// Declare the variables
int a, b, i, j, flag;
// Ask user to enter lower value
// of interval
cout << "Enter lower bound of the interval: ";
// Take input
cin >> a;
// Ask user to enter upper value
// of interval
cout << "Enter upper bound of the interval: ";
// Take input
cin >> b;
// Print display message
cout << "Prime numbers between " <<
a << " and " << b << " are: ";
// Traverse each number in the interval
// with the help of for loop
for (i = a; i <= b; i++)
{
// Skip 0 and 1 as they are
// neither prime nor composite
if (i == 1 || i == 0)
continue;
// flag variable to tell
// if i is prime or not
flag = 1;
for (j = 2; j <= i / 2; ++j)
{
if (i % j == 0)
{
flag = 0;
break;
}
}
// flag = 1 means i is prime
// and flag = 0 means i is not prime
if (flag == 1)
cout << i << " ";
}
return 0;
}
// This code is contributed by Akanksha Rai```
输出：
Enter lower bound of the interval: 1
Enter upper bound of the interval: 10
Prime numbers between 1 and 10 are: 2 3 5 7
时间复杂度： O((b-a)*(b/2))，其中a和b是下限和上限。
辅助空间： O(1)
优化解决方案：
思路是使用偶数（除2外）不是质数。
// C++程序：找出给定区间内的素数
// 包括头尾，这里的思想是试除法
#include <bits/stdc++.h>
using namespace std;
// 主函数
int main()
{
// 声明变量
int a, b, i, j;
// 让用户输入区间的下限值，注意：区间不能小于0
cout << "请输入区间的下限值：";
// 输入下限值
cin >> a;
// 让用户输入区间的上限值
cout << "请输入区间的上限值：";
// 输入上限值
cin >> b;
// 打印提示消息
cout << a << "到" << b << "之间的素数是：";
// 显式处理当 a<2 时的情况，因为0 和 1不是素数
if (a <= 2)
{
a = 2;
if (b >= 2)
{
cout << a << " ";
a++;
}
}
// 确保在进入循环前 a 是奇数
if (a % 2 == 0)
a++;
// 注意：只检查奇数
for (i = a; i <= b; i = i + 2)
{
// 用于判断 i 是不是素数
bool flag = 1;
// 只检查小于等于 j 的平方根的素数
for (j = 2; j * j <= i; ++j)
{
if (i % j == 0)
{
flag = 0;
break;
}
}
// flag = 1 表示 i 是素数，flag = 0 表示 i 不是素数
if (flag == 1)
{
if(i == 1)
continue;
else
cout << i << " ";
}
}
return 0;
}
输出:
请输入区间的下限值：1
请输入区间的上限值：10
1到10之间的素数是：2 3 5 7
时间复杂度: O((b-a)*(sqrt(b))).
辅助空间: O(1).
厄拉多塞筛法:
当 N 小于 1000 万左右时，厄拉多塞筛法是寻找小于 N 的所有素数最有效的方法之一。
步骤:
- 建立一个名为 prime[srt 到 n] 的布尔数组，并将数组的所有项初始化为 true。
- 将 prime[0] 和 prime[1] 标记为 false，因为它们不是素数。
- 从 p= sqrt 开始，对于小于等于 n 的每个素数 p，将所有大于等于 p*p 的 p 的倍数标记为合数，将 prime[i] 设置为 false。
- 最后，输出 sqrt 到 n 之间的所有素数。
以下是实现方式：
// C++程序用筛法找到给定区间内的素数
#include <bits/stdc++.h>
using namespace std;
void SieveOfEratosthenes(int srt, int n)
{
// 创建一个布尔数组"prime[srt到n]"并
// 将其所有条目初始化为true。在prime[i]中的值最终将为false，如果i不是素数，
//否则为true。
bool prime[n + 2 - srt];
memset(prime, true, sizeof(prime));
prime[0] = false;
prime[1] = false;
for (int p = srt; p * p <= n; p++) {
// 如果prime[p]没有改变，则它是一个素数
if (prime[p] == true) {
// 更新所有大于或等于它的平方的p的倍数，
// 这些数是p的倍数且小于p^2的数字已经被标记。
for (int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
// 输出所有素数
for (int p = srt; p <= n; p++)
if (prime[p])
cout << p << " ";
}
// 主函数
int main()
{
int srt = 1;
int end = 10;
SieveOfEratosthenes(srt, end);
return 0;
}
// 本代码由Susobhan Akhuli提供```
输出
2 3 5 7
复杂性分析：
时间复杂性：
筛法求素数算法的时间复杂度是 O(n*log(log(n))) ，因为它遍历了从2到n的所有数并移除每个质数的所有倍数。
在此代码中，该算法仅应用于[srt,n]的范围，将时间复杂度降低到O((n-srt+1)*log(log(n)))，对于范围[srt,n]。标记每个质数的倍数的循环从p * p到n，需要O((n-srt+1)*log(log(n)))的时间。因此，该代码的总时间复杂性为O((n-srt+1)*log(log(n))).
辅助空间：
该算法的空间复杂度为 O(n) ，这是布尔数组prime的大小。但是，数组的大小减小到n+2-srt，这是范围[srt,n]所需的数组大小。因此，该代码的辅助空间复杂度为O(n-srt+1)。