[JavaScript] 최대 공약수, 최소 공배수 구하는 알고리즘

• 최대 공약수(greatest common divisor)란?

두 수, 혹은 그 이상의 여러 수의 공통인 약수 중 가장 큰 수

 

• 최소 공배수(least common multiple)란?

두 수, 혹은 그 이상의 여러 수의 공통인 배수 중 가장 작은 수

 

ex)최대공약수

4: 1, 2, 4

12: 1, 2, 3, 4, 6, 12

4와 12의 약수 중 가장 큰 약수인 4가 최대공약수가 된다.

 

최소공배수

4: 4, 8, 12, 16, 20 ...

12: 12, 24, 36 ...

4와 12의 배수 중 가장 작은 수인 12가 최소공배수가 된다.

---

문제: 4, 12의 최대공약수와 최소공배수를 반환하는 함수를 작성하시오.

 

최대공약수와 최소고배수는 유클리드 호제법을 사용하는 것이 간단하다.

 

유클리드 호제법이란?

 

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b)  a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 

 

- a,b 를 서로 나눌때, 나누어진다면 b가 최대 공약수 이다. (a>b)

- 만약 a,b가 나누어지지 않으면 b와 a를 b로 나눈 나머지(r)를 다시 나눈다

- 서로가 나누어지면 a%b 가 최대공약수이다. 나누어지지 않는다면 위처럼 b와 r(a를 b를 나눈 나머지)를 다시 나눈다.

 

 

문제풀이

function gcdlcm(a, b) {
  var gcd = calc_gcd(a, b);
  var lcm = (a * b) / gcd;
 
    return [gcd, lcm];
}
 
function calc_gcd(a, b) {
  if (b == 0) return a;
    return a > b ? calc_gcd(b, a % b) : calc_gcd(a, b % a);
}