GCD 最大公因數

# 算 GCD

'''

最大公約數：(Greatest Common Divisor，簡寫為GCD）
最小公倍數:（英語：Lowest Common Multiple，簡寫為LCM）

1. 有兩個數x和y, 例如12和18 尋找出小數， 把比較小的數放在 s
2. 從1 開始累加一,例如1,2,3 這樣陸續一直加一
3. 如果發現一個數能被x和y 整除，那這個數就是我們要的最大公因數 結果是36.
4.
'''

x = 12     # 可以試試 x=546 ; y=429  or x=9 ; y=24
y = 18

if x > y:         # 選小數
    s = y   # 大數當被除數
else:
    s = x   # 小數當  除數
     
# 從1到 小數的一半  二個都可整除 的數 就是最大因數
for i in range(1, s+1):
    if((x % i == 0) and (y % i == 0)):
        gcd = i         

print(x,"和", y,"最大公因數=",gcd)



-----------------------------------------------------------------------------------------------------

# 求GCD (輾轉相除法)

# 可以試 x=546 ; y=429  or x=9 ; y=24
x=12; y=18     

if (x>y):
    x,y = y,x
 
m=x; x=y
while(m>0):
    y=x ; x=m ; m=y % x

print(x)