최대공약수와 최소공배수

04 Feb 2022 in Algorithms on Algorithms

수학 공부 한지가 언제인지 기억도 잘 나지 않지만, 다시 공부하는 기분은 좋다.

알았던 것들을 전혀 기억하지 못하고 다시 공부해야 알아가는 기분이 묘한데 또 새로운 성취감이 있다.

수학은 이해력이 좋아야 한다고 하지만, 사실 기본적으로 공식은 다 외워야 되지 않을까?

그냥 외우자 ㅠ

유클리드 호제법

두 양의 정수 a,b (a>b)에 대하여 a=bq+r (0≤r<b) 라 하면, a,b의 최대공약수는 b,r의 최대공약수와 같다.

즉, gcd(a, b) = gcd(b, r) r=0이라면, a,b의 최대공약수는 b가 된다.

// a>b 이어야 한다!

const gcd = (a, b) => {
  while (b !== 0) {
    temp = b;
    b = a % b;
    a = temp;
  }
  return a;
};

a = 27, b = 18일때 나머지는 9
 => 그럼 a = 18, b = 9로 바꿔준다.

 :: b를 a로, 나머지를 b로 변경
이 과정을 나머지가 0이 될때까지 반복~

나머지가 0일때 b가 최대공약수

const lcd = (a * b) / gcd(a, b);

두 수의 최소공배수는 두 수의 곱을 두 수의 최대공약수로 나눈 값과 같다.

Gryffindor0ne