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)。