최대공약수(GCD) 와 최소공배수 (LCM)

최대공약수(GCD : Greatest Common Divisor)

• 최대공약수는 줄여서 GCD라 불림.
• 두 수 A,B의 최대공약수 G는 A,B의 공통된 약수 중에서 가장 큰 정수. (약수: N을 나눌수 있는 수)
• 최대공약수를 빠르게 구하는 방법 - 유클리드 호제법을 사용
• GCD(a,b) = GCD(b,r) r이 0이면 그 때 b가 최대 공약수가 된다.  ex) GCD(24,8) = GCD(16,8) = GCD(8,0) = 8
•  

---

최대공약수 구현

재귀함수를 사용한 유클리드 호제법

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

---

세 수의 최대공약수

• GCD(a,b,c) = GCD(GCD(a,b),c)
• N개의 수 도 같은 방식으로 구할 수 있음.

---

최소공배수(LCM : Least Common Multiple)

• 최소공배수는 줄여서 LCM이라 불림.
• 두 수의 최소공배수는 두 수의 공통된 배수중 가장 작은 정수
• 최소공배수는 GCD를 응용하여 구할 수 있음.
• 두 수 a,b의 최소공배수 L = g * (a/g) * (b/g)

---

 

예제문제

2609번: 최대공약수와 최소공배수 (acmicpc.net)

2609번: 최대공약수와 최소공배수