(二)請用遞迴方式撰寫一函式GCD，輸入為2個正整數 ，其傳回 為此2個正整數之最大公 因數。（7分）

int GCD(int a, int b){

    while(b != 0) { 

        int r = a % b; 

        a = b; 

        b = r; 

    }

    printf("%d",a);   

}

int main()

{

    int a,b;

    printf("請輸入2個整數");

    scanf("%d %d",&a,&b);

    GCD(a,b);

}

另一種解法用短除法。

int GCD(x, y){
    int i = 1;
    while(true){
        i++;
        if (x%i==0 and y%i == 0){
            return i * GCD(x/i, y/i);
            if [(i^2>=x) or (i^2>=y)
                black;
        }
    }
}

1. int GCD(int N1, int N2)
2. {
3. if(N1>0 && N2>0)
4. {
5. if(N1>=N2)
6. N1=N1%N2;//如果N1大於N2，就使用輾轉相除法，N1除以N2後的餘數，需要保留(商數不需要當作下一次計算的數值)，N1原本的數值也用不到了，可以把N1取代為相除後的餘數
7. else
8. N2=N2%N1;
9.  
10. if(N1>0&&N2>0)
11. return GCD(N1,N2);
12. else if(N1==0)
13. return N2;
14. else if(N2==0)
15. return N1;
16. }
17.  
18. }