GCD & LCM

1. 최대공약수 GCD(Gratest Common Divisor)

 

공통된 약수 중 가장 큰 것

 

2. 최소공배수 LCM(Least Common Multiple)

 

공통된 배수 중 가장 작은 것

최소공배수 = 두 자연수의 곱 / 최대공약수

---

< 유클리드 호제법(Euclidean Algorithm) >

 

2개의 자연수를 입력 받아 최대공약수를 구하기 위해선 2부터 두 자연수 중 작은 자연수까지 나누어보면 가장 큰 공약수를 구할 수 있다. 그러나, 이 방법으로 최대공약수를 구하게 되면 시간 복잡도가 O(N)이 된다. 보다 효율을 높이기 위해서 유클리드 호제법이란 알고리즘을 사용하면 시간 복잡도를 O(logN)으로 줄일 수 있다.

 

호제법이란? 상대방 수를 나누어서 결국 원하는 수를 얻는 방법

 

 

X % Y = R일 때 (단, X > Y), X와 Y의 최대공약수는 Y와 R의 최대공약수와 같다. 따라서 나머지 R이 0이 될 때까지 Y와 R의 나머지 연산을 반복한다.

 

X = 85, Y = 51이라면

85 % 51 = 34, Y = 51 / R = 34

51 % 34 = 17, Y = 34 / R = 17

34 % 17 = 0, Y = 17 / R = 0 따라서 최대공약수는 17

 

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