유클리드 호제법으로 최대공약수 최소공배수 구하기

개념

2개의 자연수 a,b에서 a를 b로 나눈 나머지를 r이라 한다면 (단 a > b), a와 b의 최대공약수는 b와 r의 최대 공약수와 같다. 이 성질에 따라 b를 r로 나눈 나머지 r`를 구하고, 다시 r을 r`으로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

 

최대공약수

// a > b 일 때,

int gcd(int a, int b) {
    while (b > 0) {
        int tmp = a;
        a = b;
        b = tmp % b;
    }
    
    return a;
}

반복문을 사용하여 위와 같이 표현할 수 있다.

// a > b 일 때,

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

또한 재귀 호출을 사용하여 위와 같이 표현할 수 있다.

 

최대공약수를 활용하여 최소 공배수 구하기

정수 a,b의 최대공약수 G에 대하여 a = Gx, b = Gy (단 x,y는 정수)을 만족하는 서로소 관계의 x와 y가 존재한다. 

* 서로소: 어떤 두 정수의 최대공약수가 1이라는 뜻이다.

최소공배수는 x*y에 최대공약수 G를 곱한 Gx*y이기 때문에, a와 b를 곱한 값에 최대공약수 G를 나누어 주면 최소공배수를 구할 수 있다.

 

최소공배수

int lcm(int a, int b) {
	return a * b / gcd(a,b);
}