LV1- 최대공약수와 최소공배수

 

최대공약수

• 최대공약수는 두 수 A와 B의 공통된 약수 중에 가장 큰 정수이다.
• 최대공약수를 구하는 가장 쉬운 방법은 2부터 min(A, B)까지 모든 정수로 나누어보는 방법이다.

최소공배수

• 두 수, 혹은 그 이상의 여러 수의 공통인 배수 중 가장 작은 수이다.
• lcm을 1부터 시작하여 점차 lcm++하면서 각각의 두 수를 lcm으로 나누었을 때 나머지 값이 0인지를 비교한다.

function solution(n, m) {
  let gcd = 1; // 최대공약수
  let lcm = 1; // 최소공배수

  // 최대공약수를 구하는 방법 -> 2부터 min(n,m)까지 모든 정수로 나누어본다.
  for (let i = 2; i <= Math.min(n, m); i++) {
    if (n % i === 0 && m % i === 0) {
      //만약에 둘 다 공통으로 나누어지는 수가 있다면
      gcd = i; // 그 값을 최대공약수로 지정. 제일 마지막으로 gcd에 저장된 수가 최대 공약수.
    }
  }

  // 최소공배수를 구하는 방법 -> 둘 모두 공통으로 나누어 떨어지는 최소의 수를 구한다음 나온다.
  while (true) {
    if (lcm % n === 0 && lcm % m === 0) {
      break;
    }
    lcm++; //참일때까지 lcm을 계속 증가시킨다.
  }

  let answer = [gcd, lcm];
  return answer;
}

 

참고 블로그

 

https://velog.io/@devjade/JavaScript%EB%A1%9C-%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98GCD-%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98LCM-%EA%B5%AC%ED%95%98%EA%B8%B0

JavaScript로 최대공약수(GCD), 최소공배수(LCM) 구하기