hyeoneee's blog

두수 의 최대 공약수를 구하는 알고리즘이다. 

임의의 두 자연수 a, b가 주어졌을때. 둘중 큰 값이 a라고 가정한다면,

a를 b로 나눈 나머지를 n 이라고 하면 (a%b = n)

n이 0일때, b가 최대 공약수(GCD)이다.

만약 n이 0이 아니라면, a에 b값을 다시 넣고 n를 b에 대입 한 후 다시 위에 step2부터 반복하면 된다.

ex) a = 12 , b = 8 

1) 12 % 8 = 4 ( a % b = n )

2 ) 8 % 4 = 0 ( a % b = 0 이면 b가 최대공약수 )

따라서 a, b의 최대 공약수는 4 이다

1. 반복문

int gcd(int a, int b){
    if(a<b){ // a가 항상 큰값 
        int tmp = a;
        a = b;
        b = tmp;
    }
    
//b가 0이 될때까지(a%b), 반복문을 돌게되고, b가 0인 순간의 a를 GCD로 판단하고 리턴합니다.
    while(b!=0){
        int n = a % b;
        a = b;
        b = n;
    }
    return a;
}

2. 재귀

 static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }