GCD, LCM

최대공약수, 최소공배수 가끔 등장하는 알고리즘이다. 피보나치수열 처럼 알면 간단하게 풀 수있어서 정리하고 넘어가보자!

최대공약수

Greatest Common Divisor (GCD)

최대공약수는 유클리드 호재법으로 계산한다. 식은 아래와 같다. 재귀함수로 작성하면 된다.

//GCD
private int getGCD(int a, int b){
	if(a%b==) return b;
    return getGCD(int b, a%b);
}

최소공배수

Least Common Multiple (LCM)

최소공배수는 두 수(a, b)의 곱을 최대공약수로 나눠주면 구할 수 있다. 식은 아래와 같다. 위의 getGCD 함수를 이용하면 된다.

//LCM
private int getLCM(int a, int b){
	return a*b/getGCD(a,b);
}