迹忆客 专注技术分享

本篇文章指导使用简单、直观的方法和高效的平方根方法生成给定范围内的所有质数。

质数

质数是可以被一整除或只能被其自身整除的数； 例如，17 是一个只能被 1 或它本身整除的数字。 质数 P 的唯一可能因子是 P * 1。

让我们看一下质数集：

Set of Prime Numbers = {2, 3, 5 , 7, 11, 13, 17, 23, .....,89, 97, .... }

在C++中，我们可以编写这样的场景，生成某个范围内的质数，甚至可以判断一个数是否为质数。

在 C++ 中生成质数

检查一个数是否为质数背后的逻辑是检查其模数，所有数最多为该数的一半。 如果它与任何数的模数为 0，则该数不是质数； 否则，它是质数。

让我们看看最简单、最直观的方法：

#include <iostream>
using namespace std;

int main() {

  int start = 0, end = 100, n;
  bool ifPrime = true;

  cout << "Prime numbers in between " << start << " and " << end << " are the following: " << endl;

  while (start < end) {
    ifPrime = true;

    if (start == 0 || start == 1) {
      ifPrime = false;
    }

    for (n = 2; n <= start/2; ++n) {
      if (start % n == 0) {
        ifPrime = false;
        break;
      }
    }
    if (ifPrime)
      cout << start << ", ";

    ++start;
  }

  return 0;
}

我们在上面的代码段中取了两个变量，start 和 end。 起始变量初始化为零，结束变量初始化为 100，因为我们需要从 0 到 100 的质数。

该范围可以随时更改，也可以作为用户的输入。

我们从头到尾创建了一个循环； 在那个循环中，我们做了另一个 for 循环来检查起始数字是否可以被数字的一半整除。 这是因为，对于一个非质数N，只能存在数为a和b的因数使得a*b，其中a<N/2且b<N/2。

因此，如果内部 for 循环让 n 接近起始值的一半，则循环终止，并且数字在第 25 行打印出来，因为 ifprime 仍然为真。 但是，如果 n 的任何值都能正确地除以起始值，则第 19 行的条件变为真，将 ifprime 设置为假并终止 for 循环。

输出：

在 C++ 中使用 sqrt() 方法生成质数

前面讨论的简单质数计算方法效率低下，因为它仍然需要我们除以数字的一半来检查它是否是质数。 但是，我们可以利用数学事实来降低程序运行时间的复杂性。

该程序从以下事实中得到帮助：对于等于数字 N 的因子 a*b ，a 或 b 必须小于或等于 N 的平方根。例如，对于 36，可能的因子对是 (9*4), (18*2), (12*3), (6*6)，所以每一对的a或b都小于36的平方根。

因此，要否定一个数 N 不是质数，我们只需要检查它是否可以被任何小于 N 的平方根的数整除。 如果不是，则表示该数是质数。

现在，让我们编写场景代码：

#include <iostream>
#include <math.h>
using namespace std;

int main() {

  int start = 0, end = 100, n;
  bool ifPrime = true;

  cout << "Prime numbers in between " << start << " and " << end << " are the following: " << endl;

  while (start < end) {
    ifPrime = true;

    if (start == 0 || start == 1) {
      ifPrime = false;
    }

    for (n = 2; n <= sqrt(start); ++n) {
      if (start % n == 0) {
        ifPrime = false;
        break;
      }
    }
    if (ifPrime)
      cout << start << ", ";

    ++start;
  }

  return 0;
}

我们已经创建了一个从头到尾的循环，在该循环中，我们将对数字求平方根，这将是内循环的截断数。

内部循环将检查当前数字是否可以被任何数字整除直到其平方根。 如果不是，我们将其打印为质数。

输出结果：