LearnApplyShare

[알고리즘] 최대공약수 최소공배수

April 24, 2018 - [gcd, lcm, 유클리드호제법]

유클리드 호제법

두 자연수 a, b에 대하여

  1. a가 b로 나누어 떨어진다면 두 수의 최대공약수는 b 이다
  2. a가 b로 나누어 떨어지지 않았다면 두수의 최대공약수는 b 와 a%b 의 최대공약수와 같다

이를 js코드로 작성하면 아래와 같다

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


그럼 최소공배수는?

두수 a, b에 대하여 최대공약수를 G 최소공배수를 L이라 할 때 다음 등식이 성립된다
a * b = L * G

그러므로, L = ( a * b ) / G 가 된다.

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


n개 수의 최소공배수는?

n개의 자연수 배열을 입력으로 받아서 n개 수의 최소공배수를 리턴하는 함수

function nlcm(num) {
  function gcd(a,b) {
    return a%b ? gcd(b, a%b) : b;
  }
  function lcm(a,b){
    return a*b/gcd(a,b);
  }
  return num.reduce(lcm);
}


Ref.