任務(wù)031描述

用Python編寫一個程序，用于計算兩個整數(shù)的最大公約數(shù)。

分析及示例

計算最大公約數(shù)有很多算法，例如“輾轉(zhuǎn)相除法”，在這里用最簡單的方式。首先將兩個數(shù)相除，如果可以整除，那么被除數(shù)就是最大公約數(shù)。否則就從被除數(shù)的一半依次減1去整除，直至同時被兩個數(shù)整除為止。

示例算法:

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))

輸出結(jié)果：

1
27