유클리드 호제법을 이용한 최소공배수 찾기

 

최소공배수는 a * b 를 a와 b의 최대공약수로 나누면 쉽게 구할 수있다.

 

최대공약수를 찾기위해 유클리드 호제법을 이용하면 쉽다.

 

유클리드 호제법이란, a 와 b의 최대공약수를 구하기위해 a%b=c를 사용한다.

c가 0이라면 b가 최대공약수이고, c가 0이 아니라면 gcd(a,b) = gcd(b,c)를 계산하면 된다.

 

15와 6의 최대공약수를 구하자면 15%6 = 3이므로 gcd(15,6) = gcd(6,3)과 같고 

gcd(6,3)은 6%3 = 0 이므로 3이 최대공약수가 된다.

 

이를 코드로 구현하면 아래와 같다.

int gcd(int a, int b){
	if(b==0) return a;
    return gcd(b, a%b);
}

 

---

추가로 확장 유클리드 알고리즘이 존재하는데, 이는 ax + by = c 에서 c = gcd(a,b)일 때 x와 y의 값을 구할 수 있다.

 

int extgcd(int a, int b, int& x, int& y) {
	int g = a; x = 1; y = 0;
	if (b != 0) {
		g = extgcd(b, a % b, y, x);
		y -= (a / b) * x;
	}
	return g;
}