[백준] 5347 LCM - Node.js

5347 LCM

문제

두 수 a와 b가 주어졌을 때, a와 b의 최소 공배수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 n이 주어진다. 다음 n개 줄에는 a와 b가 주어진다. a와 b사이에는 공백이 하나 이상 있다. 두 수는 백만보다 작거나 같은 자연수이다.

출력

각 테스트 케이스에 대해서 입력으로 주어진 두 수의 최소공배수를 출력한다.

예제 입력 1	예제 출력 1
3
15 21	105
33 22	66
9 10	90

풀이

접근

A,B 의 최소 공배수 LCM 을 구하는 문제.
두 수의 공통 배수 중 가장 작은 값

LCM = (A*B) / GCD

유클리드 호제법
GCD: 최대 공약수

• A,B 의 GCD = A/B의 나머지 R,B 의 GCD
• GCD(A,B) = GCD(B,R)
• 반복 적용해서 나머지가 0이 될때까지 수행.
  나머지가 0이 되었을 때의 B가 최대 공약수 GCD

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

코드

const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let count=0;

rl.on('line', (input) => {
    if(count===0){
        count=Number(input);
    }else{
        const [a, b]= input.trim().split(' ').map(Number);
        const result = (a * b) / solution(a, b);
        console.log(result);
        count--;
        if(count===0){ rl.close();}
    }
});

function solution(a, b){
    if(b === 0){
        return a;
    }else{
        return solution(b, a % b);
    }
}