[Algorithm] GCD, LCM

최대공약수(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이상 부터는 헤더에 gcd,lcm 함수가 추가되어 있으며 유클리드 호제법으로 구현되어 있다.