C++判断两个数之间的素数方法 |21xrx.com

C++判断两个数之间的素数方法

2023-06-28 07:50:36 深夜i -- --

C++ 判断两个数素数方法

在C++中，判断两个数之间的素数可以采用两种方法：暴力枚举法和筛法。

暴力枚举法：

暴力枚举法即遍历从m到n的所有整数，判断这些整数是否为素数。具体来说，我们可以使用一个循环来遍历这些整数，并在每个整数上运用另一个循环来判断该整数是否为素数。判断素数的方法是从2到该整数的平方根之间找到能整除该整数的数，如果找到了，就说明该整数不是素数。如果遍历完整个区间，也没有找到能整除该整数的数，就说明该整数是素数。

代码如下：


#include <iostream>
#include <cmath>
using namespace std;
int main()
{
  int m, n;
  bool isPrime;
  cout << "Enter two numbers: ";
  cin >> m >> n;
  for (int i = m; i <= n; i++)
  {
    isPrime = true;
    for (int j = 2; j <= sqrt(i) && isPrime; j++)
    {
      if (i % j == 0)
      
        isPrime = false;
      
    }
    if (isPrime && i != 1)
    
      cout << i << " is prime." << endl;
    
  }
  return 0;
}

筛法：

筛法是一种更高效的方法，它可以在O(n)的时间内求出从1到n之间的所有素数。具体来说，我们可以先使用一个数组来记录每个数是否为素数，然后用质数来筛掉非质数。具体步骤如下：

1. 将2至n的所有正整数存入一个数组中，标记它们都为素数。

2. 从2开始，将每个素数的倍数标记为非素数。

3. 重复步骤2，直到所有小于n的素数都已经标记过。

代码如下：


#include <iostream>
#include <cstring>
using namespace std;
int main()
{
  int m, n;
  bool isPrime[100001];
  memset(isPrime, true, sizeof(isPrime));
  cout << "Enter two numbers: ";
  cin >> m >> n;
  for (int i = 2; i * i <= n; i++)
  {
    if (isPrime[i])
    {
      for (int j = i * i; j <= n; j += i)
      {
        isPrime[j] = false;
      }
    }
  }
  for (int i = m; i <= n; i++)
  {
    if (isPrime[i])
    
      cout << i << " is prime." << endl;
    
  }
  return 0;
}

综上所述，以上两种方法都可以判断两个数之间的素数，但是筛法比暴力枚举法更高效，适用于大规模求素数的情况。

上一篇: idea打包java可执行jar包

下一篇: C++中类的成员详解

评论区

()

相似文章