160. 輾轉相除法

Task Description
輾轉相除法
給定兩個正整數a、b，請利用遞迴找出兩數之最大公因數。

Hint

GCD.h

打上 function header 以及相關的設定。

int GCD(int t, int v);

GCD.c

撰寫程式碼後對應上傳。

#include "GCD.h"
 
int GCD(int t, int v) {
    / add your code /
}

main.c

這個檔案無法更改也無須上傳。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#include <stdlib.h>
#include "GCD.h"
 
int main() {
    int a, b;
 
    scanf("%d", &a);
    scanf("%d", &b);
    int temp;
 
    if (b > a) {
        temp = a;
        a = b;
        b = temp;
    }
    printf("%d\n", GCD(a, b));
    return 0;
}

Input Format

第一列輸入為 a、b。
Note: 0<a、b≤1000

Output Format

印出兩數之最大公因數

Sample Input

1
18 12

Sample Output

1
6

Sample Input

1
45 75

Sample Output

1
15