최대공약수

최대공약수

 

특정한 두 수가 주어졌을 때 두 수 의 최대공약수(GCD)를 구하는 코드를 작성한다.

 

 

 

1. 풀이

1.1 풀이 방법

두 수 M과 N의 최대 공약수를 gcd(M, N)이라고 할 때, 다음과 같은 식이 성립한다. (M > N)

 

gcd(M, N) = gcd(N, M % N) (증명은.. 위키에 있다..!)

 

따라서 위의 식을 M % N = 0이 될 때까지 반복해서 적용한다.

M % N = 0이 성립한다는 것은 M이 N의 배수가 된다는 뜻이니까 gcd(M, N) = N이 된다.

 

 

 

1.2 코드

1.2.1 gcd

[gcd]

private int gcd(int M, int N) {   //최대공약수를 구하는 메서드
    if (M < N) {
        int temp = M;
        M = N;
        N = temp;
    }
    while (M % N != 0) {
        int tempM = M;
        M = N;
        N = tempM % N;
    }
    return N;
}