C++ 求 Gcd 程序

能够整除两个整数的最大整数称为这两个数的 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;

  // 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;
}

这个程序逻辑很简单。

在这个程序中，较小的整数存储在 n2 中，n1 和 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;
}

输出

Enter two numbers: 16
76
HCF = 4

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

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

这个过程一直持续到两个数相等为止，此时它们的值就是 HCF。

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

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

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

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