[백준] 2609

최대공약수와 최소공배수

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

풀이

const getGCD = (main, div) => {
  if (div === 0) return main;
  else return getGCD(div, main % div);
};

const gcdlcm = () => {
  let input = require("fs")
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split(" ")
    .map((n) => {
      return parseInt(n);
    });

  let main, divider;
  input[0] > input[1]
    ? ((main = input[0]), (divider = input[1]))
    : ((main = input[1]), (divider = input[0]));

  let gcd = getGCD(main, divider);
  console.log(`${gcd}\n${(input[0] * input[1]) / gcd}`);
};

gcdlcm();

반성회

유클리드 호제법을 사용하는 문제

• 최대공약수

  1. 두 수 a, b 중 작은 수 b로 큰 수 a를 나눈 나머지 b % a를 b에 대입하고, b를 a에 대입
  2. b가 0이 될 때까지 반복

• 최소공배수

  a와 b를 곱하여 최대공약수로 나누기