최대공약수, 최소공배수의 간단한 정의를 알아보자.
약수 : 어떤 수를 나누어 떨어지게 하는 수이다.
공약수 : 어떤 두 수를 동시에 나누어 떨어지게 하는 수이다.
최대공약수(Greatest Common Devisor, GCD) : 두 수의 공약수 중 가장 큰 수를 말한다. (재귀함수로도, 그냥으로도 구현해보자)
공배수 : 어떤 두 수의 공통된 배수이다.
최소공배수(Least Common Multiple) : 두 수의 공배수 중 가장 작은 수를 말한다. 최대공약수를 먼저 구한 다음에 두 수를 곱하고 최대공약수로 나눠주면 최소공배수가 나온다.(A*B/최대공약수)
대부분의 경우, 수학적으로 계산할 때 최대공약수와 최소공배수는 소인수분해를 이용하는 방법으로 구하게 된다. 하지만
컴퓨터를 이용해 최대공약수를 찾을 때는, 소인수분해를 하기 보다는 유클리드 호제법(Euclidean Algorithm)이라는 알고리즘(문제를 풀기 위해 정해진 절차)를 사용하는 것이 더 빠르다. 유클리드 호제법은 다음 정리로부터 기인합니다.
를 로 나눈 몫을 라 하고, 나머지를 이라 하자. 이 때, 이다.
즉, 아래와 같은 수식으로 나타낼 수 있다.
두 수를 예로 들어보면 이해가 편할수도 있다.
24와 18을 예로 들어보자. 24를 18로 나눈 몫은 1이고, 나머지는 6이다. 그렇다면 18과 6을 보자. 18을 6으로 나눈 몫은 3, 나머지는 0이다. 직접 최대공약수를 구해보면 gcd(24, 18) = gcd(18, 6) = 6임을 알 수 있다.
그렇다면 코드로는 어떻게 구현하면 될까? 재귀함수를 돌리면 gcd(24, 18) => gcd(18, 6) => gcd(6, 0)이다. 그렇다면 두번째 숫자인 b가 0이 되었을 때의 a를 반환하면 최대공약수를 구할 수 있다는 것을 알 수 있다.
a가 더 크던 b가 더 크던 반복이 한번 더 늘어나는 차이기 때문에 a,b의 크기는 상관없다.
최소공배수는 위에서 구한 최대공약수를 이용해 (a * b / 최대공약수)로 간단하게 구할 수 있다.
정리하자면,
최대공약수(GCD) - 유클리드 호제법 -> gcd(A,B) = gcd(B,R)
최소공배수(LCM) - A * B / 최대공약수
그렇다면 두 수가 주어졌을 때, 최대공약수와 최소공배수를 구하는 코드를 작성해보자.
GCD, LCM 구현(java)
public static int gcd(int num1, int num2){
if(num2 == 0) return num1;
else return gcd(num2, num1 % num2);
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int num1 = sc.nextInt(), num2 = sc.nextInt();
int gcd = gcd(num1, num2);
System.out.println(gcd); // GCD
System.out.println(num1 * num2 / gcd); // LCM
}
GCD, LCM 구현(Python)
파이썬은 math 모듈에 math.gcd()라고 최대공약수를 구하는 함수가 있다.
3.9부터는 math.lcm()도 있다고 한다.
def gcd(a, b): # 최대공약수
while b > 0:
a, b = b, a % b
return a
def lcm(a, b): # 최소공배수
return a * b / gcd(a, b)2개 이상의 최대공약수, 최소공배수를 구하는 방법도 별반 다르지 않다.
최대공약수는 먼저 두 수의 최대공약수를 구하고, 그 최대공약수와 다른 수의 최대공약수를 구하는 작업을 반복하면 된다.
최소공배수는 두 수의 최소공배수를 구하고, 최소공배수와 다른 수의 최대공약수를 구하고 이를 통해 최소공배수를 구하는 작업을 반복하면 된다.
즉, 그냥 반복하면 된다.
