###### tags: `python-TQC`
# TQC+ 程式語言Python 508 最大公因數

1. 題目說明:
請開啟PYD508.py檔案，依下列題意進行作答，計算兩個正整數的最大公因數，使輸出值符合題意要求。作答完成請另存新檔為PYA508.py再進行評分。。

2. 設計說明：
請撰寫一程式，讓使用者輸入兩個正整數x、y，並將x與y傳遞給名為compute()的函式，此函式回傳x和y的最大公因數。

3. 輸入輸出：
輸入說明
兩個正整數（以半形逗號分隔）

x,y

輸出說明
最大公因數

> https://zh.wikipedia.org/wiki/%E6%9C%80%E5%A4%A7%E5%85%AC%E5%9B%A0%E6%95%B8#%E4%BA%92%E8%B4%A8%E6%95%B0
>

#method 1 <值因數分解法>
def compute(x,y): 
    gcd = 1 
    for i in range(2,(min(x,y)+1)):
        if x%i == 0 and y%i == 0:
            gcd = i
            
    return gcd


(x,y) = eval(input())
print(compute(x,y))

#method 2 很容易理解的方法<質因數分解法>
def compute(x,y):
    gx = []
    for i in range(1,x):
        if x%i == 0:
            gx.append(i)
    gy = []
    for i in range(1,y):
        if y%i == 0:
            gy.append(i)
    max1 = [a for a in gx if a in gy] #找gx,gy最大值
    return(max(max1))

(x,y) = eval(input())
print(compute(x,y))

#method 3 偷吃步方法<直接呼叫數學模組的gcd>
import math
def compute(x,y):
    g = math.gcd(x,y)
    return g

(x,y) = eval(input())
print(compute(x,y))

**維基百科的寫法,研究了很久,但我腦筋還是很難一時轉過來(利用輾轉相除法的概念,程式執行效率較佳)**