Python程序查找最大公因数（HCF）或最大公约数（GCD）

在此示例中，您将学习使用两种不同的方法查找两个数字的GCD：函数和循环以及欧几里得算法

要理解此示例，您应该了解以下Python编程主题：

两个数的最大公因数(H.C.F)或最大公约数(G.C.D)是能完美地将两个给定数相除的最大正整数。例如，H.C.F(12, 14)等于2。

源代码：使用循环

示例# Python程序查找两个数字的H.C.F

# 定义一个函数

def compute_hcf(x, y):

# 选择较小的数字

if x > y:

smaller = y

else:

smaller = x

for i in range(1, smaller+1):

if((x % i == 0) and (y % i == 0)):

hcf = i

return hcf

num1 = 54

num2 = 24

print("H.C.F. 是", compute_hcf(num1, num2))

输出结果H.C.F. 是 6

这里，存储在变量num1和num2中的两个整数被传递给compute hcf()函数。该函数计算H.C.F.这两个数字并返回它。

在这个函数中，我们首先确定两个数字中较小的那个F只能小于或等于最小的数。然后我们使用一个for循环从1到那个数字。

在每次迭代中，我们检查我们的数字是否完美地将两个输入数字相除。如果是这样，我们将这个数字存储为H.C.F.，在循环结束时，我们得到的最大的数字完美地将两个数字相除。

上述方法易于理解和实施，但是效率不高。查找HCF的一种更有效的方法是欧几里得算法。

欧几里得算法

该算法基于以下事实：两个数字的HCF也将它们的差除。

在此算法中，我们将较大者除以较小者，然后取余数。现在，将较小者除以该余数。重复直到剩余为0。

例如，如果我们想求54和24的hcf，我们用54除以24。余数是6。24除以6，余数是0。因此，6是必需的hcf

源代码：使用欧几里得算法

示例# 函数查找HCF的使用欧几里德算法

def compute_hcf(x, y):

while(y):

x, y = y, x % y

return x

hcf = compute_hcf(300, 400)

print("The HCF is", hcf)

在这里我们循环直到y变为零。该语句x, y = y, x % y在Python中交换值。单击此处以了解有关在Python中交换变量的更多信息。

在每次迭代中，我们同时将y的值放在x中，其余的(x % y)放在y中。当y变为0时，我们得到x的hcf。

gcd函数即为实现求两数最大公约数（最大公因数）的函数

求两个整数最大公约数主要的方法：
1.穷举法：分别列出两整数的所有约数，并找出最大的公约数。
2.素因数分解：分别列出两数的素因数分解式，并计算共同项的乘积。
3.短除法：两数除以其共同素因数，直到两数互素时，所有除数的乘积即为最大公约数。
4.辗转相除法：两数相除，取余数重复进行相除，直到余数为0时，前一个除数即为最大公约数。

gcd函数的一些实现方法：

【C++】gcd函数的写法

库函数也有已经实现的gcd函数：

int k=__gcd(n,m);

#include <iostream>
#include <algorithm>
using namespace std;
int a,b;
 
int main()
{
  cin>>a>>b;
  cout<<__gcd(a,b)<<endl;
  return 0;
}

int、long long类型都可以，需要注意的是两个类型必须要相同，还有就是不能用浮点型，它头文件是algorithm。