[Algorithm] 유클리드 호제법

📌유클리드 호제법

2개의 자연수의 최대공약수(GCD)를 구하는 알고리즘

원리

• 두 개의 자연수 a, b (a > b)에 대하여, a를 b로 나눈 나머지 = r 이라고 한다면 GCD(a, b) = GCD(b, r)이다.
  (a,b의 최대공약수와 b,r의 최대공약수가 같다)
• 이 성질에 따라 a를 b로 나눈 나머지 = r을 구하고, b를 r로 나눈 나머지 = r’ 를 구해간다.
• 나머지가 0이 될 때 나눈 수가 a, b의 최대공약수이다.

최대공약수로 최소공배수 구하는 법

• 최소공배수 = (a * b) / (최대공약수)

예시

ex) 60, 48 의 최대공약수, 최소공배수?
	60 % 48 = 12
	48 % 12 = 0
	→ 최대 공약수 : 12

	→ 최소 공배수 : (60 * 48) / 12 = 240

Java 코드

private static int gcd(int a, int b) {
		while(b != 0) {
			int r = a % b;
			a = b;
			b = r;
		}
		return a;
	}