Python习题册031:计算两个数的最大公约数

任务031描述

用Python编写一个程序，用于计算两个整数的最大公约数。

分析及示例

计算最大公约数有很多算法，例如“辗转相除法”，在这里用最简单的方式。首先将两个数相除，如果可以整除，那么被除数就是最大公约数。否则就从被除数的一半依次减1去整除，直至同时被两个数整除为止。

示例算法:

def gcd(x, y):
   gcd = 1

   if x % y == 0:
       return y

   for k in range(int(y/2), 0 , -1):
       if x % k ==0 and y % k == 0:
           gcd = k
           break
   return gcd

print(gcd(12,17))
print(gcd(81,27))

输出结果：

1
27