[Js] 최대공약수(GCD) & 최소공배수(LCM) 구하기

최대공약수(GCD)

• 최대공약수는 두 수 a와 b의 공통된 약수 중에 가장 큰 정수이다.
• 최대공약수를 구하는 가장 쉬운 방법은 2부터 min(a, b)까지 모든 정수로 나누어보는 방법이다.
• 최대공약수가 1인 두 수를 서로소(Coprime)라고 한다.

 

최대공약수 구하기

See the Pen 최대공약수 by mk (@kmeijing) on CodePen.

 

유클리드 호제법으로 최대공약수 구하기

유클리드 호제법은 2개의 자연수의 최대공약수를 구하는 알고리즘이다.

• 유클리드 호제법의 기본 원리는 a를 b로 나눈 나머지를 r이라고 했을 때, 
• GCD(a, b) = GCD(b, r)과 같다는 것이다.
• r이 0이라면, 그 때의 b가 최대공약수이다.

 

See the Pen 최대공약수 - 유클리드 호제법 by mk (@kmeijing) on CodePen.

 

---

 

최소공배수(LCM)

• 최소공배수는 두 수의 공통된 배수 중에서 가장 작은 정수이다.
• a * b = gcd * lcm 과 같다.
• 그러므로, lcm = (a*b) / gcd 이다.

See the Pen 최소공배수 by mk (@kmeijing) on CodePen.