C++ 中的质数生成器

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

质数

质数是可以被一整除或只能被其自身整除的数; 例如,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,可能的因子对是 (94), (182), (123), (66),所以每一对的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;
}

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

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

输出结果: