查找 最大公约数 的 C++ 程序

在本文中，我们使用 C++ 程序实现查找两个数字的最大公约数。

本文展示了使用循环和决策语句计算两个整数（正整数和负整数）的 最大公约数 的不同方法的示例。

要理解此示例，您应该具备以下 C++ 编程 主题的知识：

• C++ if, if…else 和嵌套 if…else
• C++ for 循环
• C++ while 和 do…while 循环

可以完美地整除两个整数的最大整数称为这两个数的最大公约数。

例如，4 和 10 的最大公约数是2， 因为它是可以整除 4 和 10 的最大整数 。

示例：使用 for 循环查找最大公约数

#include <iostream>
using namespace std;

int main() {
  int n1, n2, hcf;
  cout << "Enter two numbers: ";
  cin >> n1 >> n2;

  // swapping variables n1 and n2 if n2 is greater than n1.
  if ( n2 > n1) {
    int temp = n2;
    n2 = n1;
    n1 = temp;
  }

  for (int i = 1; i <=  n2; ++i) {
    if (n1 % i == 0 && n2 % i ==0) {
      hcf = i;
    }
  }

  cout << "HCF = " << hcf;

  return 0;
}

这个程序的逻辑很简单。

在这个程序中，将 n1 和 n2 之间的较小整数 存储在 n2. 然后从 i = 1 到 i <= n2 开始循环迭代，在每次迭代中， i 增加 1。

如果两个数都可以被 i 整除然后，该数字存储在变量 hcf 中。

这个过程在每次迭代中重复。迭代完成后，两个数的最大公约数将存储在变量 hcf 中。

示例 2：使用 while 循环查找 最大公约数

#include <iostream>
using namespace std;

int main() {
  int n1, n2;

  cout << "Enter two numbers: ";
  cin >> n1 >> n2;

  while(n1 != n2) {
    if(n1 > n2)
      n1 -= n2;
    else
      n2 -= n1;
  }

  cout << "HCF = " << n1;

  return 0;
}

输出

Enter two numbers: 16
76
HCF = 4

在上面的程序中，从较大的数字中减去较小的数字，然后将该数字存储在较大的数字位置。

在这里， n1 -= n2 与 n1 = n1 - n2 相同。同样， n2 -= n1 与 n2 = n2 - n1 相同。

这个过程一直持续到两个数字变得相等，这将是两个数的最大公约数。

让我们看看这个程序在 n1 = 16 和时是如何工作的 n2 = 76 。

在这里，循环在 n1 != n2 变成 false 时终止。

在循环的最后一次迭代之后， n1 = n2 = 4, 这是 最大公约数 的值，因为这是可以除以 16 和 76 的最大数。

除此之外，我们还可以使用递归函数找到两个数字的最大公约数。