#include <stdio.h>
#include <stdlib.h>

void gcd(int a , int b ){
	int temp , r;
	r = a % b;
	
	if(r!=0){
		if(b>a){
			temp = a;
			a = b;
			b = temp;
		}
		r = a % b;
		printf("gcd(%d,%d)\n",a,b);
		a = r;
		
		gcd(a,b);
	}else{
		printf("gcd(%d,%d)\n",b,a);
		printf("\nans = %d",b);
	}
}

int main(){
	int a , b ,ans;
	printf("輸入兩個正整數 ==> ");
	scanf("%d %d",&a,&b);
	gcd(a,b);
	return 0 ;
}


//#include <stdio.h>
//#include <stdlib.h>
//
//int gcd(int a, int b) {
//    // 印出當前計算步驟
//    printf("gcd(%d,%d)\n", a, b);
//    
//    // 基本情況：如果 b 為 0，則 a 為最大公因數
//    if (b == 0) {
//        return a;
//    }
//    
//    // 遞迴計算：gcd(a,b) = gcd(b,a%b)
//    return gcd(b, a % b);
//}
//
//int main() {
//    int a, b, ans;
//    printf("輸入兩個正整數 ==> ");
//    scanf("%d %d", &a, &b);
//    
//    printf("%d\n",a % b);
//    
//    ans = gcd(a, b);
//    printf("\nans = %d\n", ans);
//    
//    return 0;
//}