유클리드 호제법

최대공약수(혹은 최소공배수)를 구할때 유클리드 호제법을 사용하면 간단하다.

 

a를 b로 나눈 나머지를 r이라고 했을때 GCD(a,b) = GCD(b,r) 과 같다.

r=0 이면 그 때, b가 최대 공약수이다.

 

//재귀함수를 사용하여 구현한 유클리드 호제법
int GCD(int a,int b){
	if(b==0){
		return a;
	}else{
		return GCD(b,a%b);
	}
}

 

 

세 수의 최대공약수는 다음과 같이 구할 수 있다.

 

GCD(a,b,c) = GCD(GCD(a,b),c)

 

네 수, N개의 숫자도 위와 같은 식으로 계속해서 구할 수 있다.

 

---

• 최소공배수는 줄여서 LCM이라고 한다.
• 두 수의 최소공배수는 두 수의 공통된 배수 중에서 가장 작은 정수
• 최소공배수는 GCD 를 응용해서 구할 수 있다.

G = GCD(A,B)

• 두 수의 a,b의 최대공약수를 g라고 했을 때
• 최송배수는 L = g * (a/g) * (b/g)이다.

AXB = GCD XLCM

LCM = A*B/G