C++ 编程：寻找最大公约数

为了理解这个示例，你应该具备以下 C++ 编程 主题的知识：

• C++ if、if...else 和 嵌套 if...else
• C++ for 循环
• C++ while 循环和 do...while 循环

两个整数能够被完美整除的最大整数被称为这两个数的最大公约数（GCD）或最高公因数（HCF）。

例如，4 和 10 的 GCD 是 2，因为它是既能整除 4 又能整除 10 的最大整数。

示例 1：使用 for 循环查找 HCF/GCD

#include <iostream>
using namespace std;

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

  // 如果 n2 大于 n1，则交换变量 n1 和 n2。
  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 将存储在变量 hcf 中。

示例 2：使用 while 循环查找 GCD/HCF

#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;
}
```**输出**

```cpp
Enter two numbers: 16
76
HCF = 4

在上面的程序中，较小的数被从较大的数中减去，然后这个数被存储在较大数的位置。

这里，n1 -= n2 和 n1 = n1 - n2 是相同的。同样地，n2 -= n1 和 n2 = n2 - n1 也是相同的。

这个过程持续进行，直到这两个数变得相等，这个相等的数就是 HCF。

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

n1	n2	n1 > n2	n1 -= n2	n2 -= n1	n1 != n2
16	76	假	-	60	真
16	60	假	-	44	真
16	44	假	-	28	真
16	28	假	-	12	真
16	12	真	4	-	真
4	12	假	-	8	真
4	8	假	-	4	假

这里，循环终止时 n1 != n2 变为 假。

在循环的最后一次迭代之后，n1 = n2 = 4。这就是 GCD/HCF 的值，因为这是可以同时整除 16 和 76 的最大数。

我们还可以使用函数递归来找出两个数的 GCD。