#03. 유클리드 호제법, 유클리드 알고리즘(Euclidean algorithm)

• 2개의 자연수 또는 정식의 최대공약수(greatest common divisor)를 구하는 알고리즘 중 하나

 

• 입력으로 두 수 m,n(m>n)이 들어온다.
• n이 0이라면, m을 출력하고 알고리즘을 종료한다.
• m이 n으로 나누어 떨어지면, n을 출력하고 알고리즘을 종료한다.
• 그렇지 않으면, m을 n으로 나눈 나머지를 새롭게 m에 대입하고, m과 n을 바꾸고 3번으로 돌아온다.

---

• 재귀 함수를 이용하는 방법

int GCD(int a, int b) {

	if (b == 0)
		return a;
	else
		return GCD(b, a%b);
}

 

• 반복문을 이용하는 방법

int GCD(int a, int b) {

	int c;

	while (b) {
		c = a%b;
		a = b;
		b = c;
	}
	return a;
}

 

---

• 이를 이용해 최소공배수(least common multiple)를 구하는 방법

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

 

최소공배수 × 최대공약수 = (두 자연수의 곱) 

→  최소공배수 = (두 자연수의 곱) / 최대공약수

 

 

ex) A = Gx, B = Gy (단, x, y는 정수)

 

→ A × B = GGxy (G는 두 수의 최대 공약수이며 x와 y는 서로소 관계)

→ A × B / G = Gxy (= 최소공배수)

 

---

※ 참고한 사이트 ※

 

myjamong.tistory.com/138

최대공약수(GCD), 최소공배수(LCM) 구하기 유클리드 호제법 알고리즘 :: 코드자몽

coding-factory.tistory.com/599

[Algorithm] 유클리드 호제법 - 최대공약수(GCD) 구하기

tech.lonpeach.com/2017/11/12/Euclidean-algorithm/

유클리드 호제법이란? - Lonpeach 기술 블로그 | Lonpeach Tech