[Java] 최대공약수, 최소공배수 구하기

유클리드 호제법 (Euclidean algorithm)

: 2개의 수에 대하여 최대공약수를 구하는 알고리즘

 

자연수 a,b 가 있고, r = a mod b (즉, r 은 a를 b로 나눈 나머지)

이 때, (a,b)의 최대공약수와 (b,r)의 최대공약수는 같다.

 

즉, 아래와 같다.

 

GCD(a,b) = GCD(b,r)

 

이 성질에 따라

1) a를 b로 나눈 나머지 r 을 구하고,

2) b를 r로 나눈 나머지 r' 을 구한다.

 

위 과정을 반복하며 나머지가 0이 될때 나눈 수가 a,b 의 최대공약수가 된다.

ex) 60과 48의 최대공약수는 ?
60 % 48 = 12
48 % 12 = 0 // 최대공약수 : 12

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

최소공배수 : (a x b) / (최대공약수)

코드

// 최대공약수 (GCD)
int gcd(int a, int b) {
	if(b == 0)
    	return a;
    // GCD(a, b) = GCD(b, r) 이므로, (r = a%b)
    return gcd(b, a%b);
}

// 최소공배수 (LCM)
int lcm(int a, int b) {
	return (a*b) / gcd(a,b);
}