[코딩테스트] 최대공약수와 최소공배수

1. 문제

프로그래머스

2. 다른 사람풀이 본 후

function solution(n, m) {
  var answer = [];

  for (let i = 1; i <= Math.min(n, m); i++) {
    if (n % i == 0 && m % i == 0) {
      answer = [i, (m * n) / i];
    }
  }
  return answer;
}

최소 공배수는  a*b/최대공약수   를 이용 했다.

 

3. 유클리드 호재법

function solution(a, b) {
  var answer = [];
  let r;
  for (var ab = a * b; (r = a % b); a = b, b = r) {}
  answer = [b, ab / b];

  return answer;
}

 

유클리드 호재법이란 a와 b의 최대공약수는 a를 b로 나눈 나머지 r과 b의 최대 공약수와 같다는 것이다.

또 r과 b의 최대공약수는 b를 r로 나눈 나머지와 r의 최대 공약수와 같다. 

이를 계속 반복하여 나머지가 0이될때 r값이 최대공약수가 된다.

 

참고한 사이트 : https://myjamong.tistory.com/138