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

참고 문제 링크

---

https://www.acmicpc.net/problem/2609

GCD & LCM

---

http://terms.naver.com/entry.nhn?docId=3338368&cid=47324&categoryId=47324

http://terms.naver.com/entry.nhn?docId=3338367&cid=47324&categoryId=47324

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

 - GCD(Greatest Common Diviser) : 최대공약수. 0이 아닌 두 개 이상의 정수의 공통되는 약수 중에서 가장 큰 수. 즉, 공약수 중에서 가장 큰 수를 의미.

 -LCM(Least Common Multiple) : 최소공배수. 0이 아는 두 개 이상의 정수의 공통되는 배수 중에서 가장 작은 수. 즉, 공배수 중에서 가장 작은 수를 의미.

 - Eucilean Algorithm : 유클리드 호제법. 2개의 자연수에서 최대공약수를 구하는 알고리즘. 호제법이라는 뜻이 두 수가 상대방 수를 나눠서 원하는 수를 구하는 법이므로, 유클리드 호제법 또한 나눠서 구하는 알고리즘.

  

구현

---

1. 두 수가 주어졌을 때, 큰 것에서 작은 것을 나눈다.

2-1. 나머지가 0일 때 : GCD = 작은 수, LCM = (처음 두 수를 곱한 값) / GCD

2-2. 나머지가 0이 아닐 때 : 두 수 중에서 작은 수와 나머지를 가지고 다시 유클리드 호제법 시행

※ 정확하고 부드러운 태클은 언제나 환영입니다.