[기초 알고리즘] 최대공약수 최소공배수 찾기(유클리드 호제법) - 자바스크립트

유클리드 호제법

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

 

유클리드 호제법에 의하면 A와 B 두 수의 최대공약수를 구할 때,
A = Bq+r의 식으로 만든 뒤 B와 r의 최대공약수를 구하는 문제로 바꿀 수 있다.
연속되는 B, r의 최대공약수에 대해서도 B = rq+r2 와 같이 재귀가 가능하다.

 

최대공약수는 A,B 모두 나누어 떨어뜨리는 최대의 약수이므로, r=0 일 때 B의 값이 최대공약수이다.

 

최대공약수 구하기

유클리드 호제법을 이용해 최대공약수를 구해보자.

 

반복문 사용하기

function gcd(a,b){ 
  let c = 0; 
  while(b !== 0){ 
    c = a % b; 
    a = b; 
    b = c; 
  } 
  return a; 
}

 

재귀함수로 만들기

function gcd(a,b){ 
  return b ? gcd(b, a%b) : a; 
}

// Arrow function 사용해보기.
const gcd = (a,b) => b ? gcd(b, a%b) : a;

 

최소공배수 구하기

앞서 최대공약수를 구했다면 최소공배수를 구하는 것은 쉽다.

 

(A,B의 최소공배수) = A * B / (A,B의 최대공약수) 로 구할 수 있다.

let lcm = a * b / gcd(a,b);