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

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

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

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

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

例如,410 的最大公约数是2, 因为它是可以整除 410 的最大整数 。

示例:使用 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;
}

这个程序的逻辑很简单。

在这个程序中,将 n1n2 之间的较小整数 存储在 n2. 然后从 i = 1i <= n2 开始循环迭代,在每次迭代中,一世 增加 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 -= n2n1 = n1 - n2 相同。同样, n2 -= n1n2 = n2 - n1 相同。

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

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

n1 n2 n1 > n2 n1 -= n2 n2 -= n1 n1 != n2
16 76 false - 60 true
16 60 false - 44 true
16 44 false - 28 true
16 28 false - 12 true
16 12 true 4 - true
4 12 false - 8 true
4 8 false - 4 false

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

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

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