GCD(최대공약수), LCM(최소공배수) C++ 구현

최대공약수(GCD, Great Common Divisor)과 최소공배수(LCM, Least Common Multiple)을 구해보자

 

최대 공약수

최대공약수는 나머지 연산을 활용하는 유클리드 호제법을 이용하여 쉽게 구할 수 있다.

 

입력으로 들어온 두 수 a,b에 대하여

b = a*k +r이라 표현하면 a,b의 최대 공약수는 a,r의 최대공약수와 같다는 원리를 이용한다.

 

1) 반복문을 사용

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

2) 재귀함수 사용

int gcd(int a, int b){
	if(b == 0) return a; // b == 0 인경우 더 이상 최대 공약수를 갖지 않아서 a 반환
    	else return gcd(b, a%b); // 유클리드 호제법을 활용하여 a,b의 최대공약수를 b,(a%b)로 구한다.
}

최소 공배수

최소 공배수는 두 수 a,b를 곱하고 최대공약수로 나누어주면 된다.

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

 

c++17이상 부터는 <numeric>헤더에 gcd, lcm 함수가 추가되었으며 유클리드 호제법으로 구현되어 있다.