Greatest Common Divisor, Least Common Multiple

1. GCD(최대공약수)

//재귀를 이용한 구현
public static int gcd(int n1, int n2) {
	if(n2==0) { return n1; }
    
	returb gcd(n2, n1%n2);	
}

 

2. LCM(최소공배수)

public static int gcd(int n1, int n2) {
	if(n2==0) { return n1; }

	return gcd(n2, n1%n2);
}

public static int lcm(int n1, int n2) {
	return n1*n2/gcd(n1,n2);
}

 

참고

- 『알고리즘 기초 1/2』