[알고리즘] 최대공약수, 최소공배수

최대공약수를 이용해서 최소공배수를 구할 수 있다.

유클리드 호제법이라고 한다.

 

	// 최대공약수
	public static long gcd(long a, long b) {
	    if (b == 0) return a;
	    return gcd(b, a % b);
	}
	
	// 최소공배수
	public static int lcm(int a, int b) {
	    return (a * b) / gcd(a, b);
	}