[백준 2609번] 최대공약수와 최소공배수(Node.js,JavaScript)

출처

https://www.acmicpc.net/problem/2609

문제

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

입력

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

출력

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

문제풀이

첫 풀이 시도

const input = require("fs").readFileSync("/dev/stdin").toString().trim();
var N = input.split(" ").map(Number);
var M = "";
while (true) {
  if (N[0] % 2 == 0 && N[1] % 2 == 0) {
    N[0] /= 2;
    N[1] /= 2;
    M *= 2;
  } else if (N[0] % 3 == 0 && N[1] % 3 == 0) {
    N[0] /= 3;
    N[1] /= 3;
    M *= 3;
  } else if (N[0] == 2 || (N[0] == 3 && N[1] == 2) || N[1] == 3) {
    console.log(M + "\n" + M * N[0] * N[1]);
    break;
  }
}

처음에는 2나 3중 같은 수로 나누어떨어지는 수로 각 입력받은 수를 나누어서 M 나눈 값을 곱해주어 최대공약수로 사용하는 방법을 시도해보았다.
하지만 이런 방법으로는 시간초과가 발생하고 말았다.
다른 방법을 찾아보았고 최대공약수를 구하는 방법중 유클리드 호제법이라는 것을 알게 되었다.

const input = require("fs").readFileSync("/dev/stdin").toString().trim();
var N = input.split(" ").map(Number);
const [a,b] = N;
while(N[0] % N[1] !== 0){
    let n = N[0]%N[1];
    if(n!==0){
        N[0] = N[1];
        N[1] = n;
    }
}
console.log(N[1]);
console.log((a*b)/N[1]);

유클리드 호제법을 적용한 후 코드의 모습이다.

<유클리드 호제법>
1. 먼저 두개의 수를 서로 나눈 나머지를 구한다. ex) 1071 % 1029 = 42
2. 두 수중 작은 수를 다시 나머지로 나눈다. ex) 1029 % 42 = 21
3. 나누어 떨어질때까지 반복한다.
4. 나누어떨어지면 나눈 수가 최대공약수가 된다. ex) 42 % 21 = 0 최대공약수는 21

최소공배수 = A X B / 최대공약수

유클리드 호제법을 숙지하자.