알고리즘 - 유클리드 호제법 (최대 공약수, 최소 공배수)

// 최대 공약수 (GCD)
// Greatest Common Divisor
// GCD(a,b) = GCD(b, a % b); 
private static int gcd(int a, int b) {
	if (b == 0) return a;
    
    return gcd(b, a % b);
}

// 최소 공배수 (LCM)
// Least Common Multiple
// int A = a*d, int B = b*d 이므로 a,b는 서로소이고 d는 최대 공약수임
private static int lcm(int a, int b) {
	return a * b / gcd(a, b);
}

자세한 설명은 이곳을 참고하자.