[Java] 최대공약수(GCD)와 최소공배수(LCM)

최대공약수(GCD)

GCD - Greatest Common Divisor
가장 큰 공통된 약수
ex) 12와 8의 최대공약수 = 4

유클리드 호제법으로 최대공약수를 구할 수 있다.
a % b = r
12 % 8 = 4
8 % 4 = 0
4 % 0 -> b가 0일 때, a값이 gcd가 된다. 따라서 gcd = 4

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

최소공배수(LCM)

LCM - Least Common Multiple
가장 작은 공통된 배수
ex) 12와 8의 최소공배수 = 24

public int lcm(int a, int b){
	return a*b/gcd(a,b);
}