기초 알고리즘 1/2. 300 - 수학1
1934번. 최소공배수

문제

1934번 문제 링크

solution

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const iter = Number(input.shift());

let ans = [];

for(let i = 0; i < iter; i++){
    let [a, b] = input[i].split(" ").map((item) => Number(item));
    
    let originala = a;
    let originalb = b;
    
    // 유클리드 호세법
    // while문이 끝나면 최대공약수는 b가 된다.
    while(a % b !== 0){
        let r = a % b;
        
        if(r !== 0){
            a = b;
            b = r;
        }
    }
    
    // 최소공배수
    // 최소공배수 = 자연수1 * 자연수2 / 최대공약수
    let min = originala * originalb / b;
    ans.push(min);
}

console.log(ans.join("\n"));

최소공배수는 두 자연수의 곱을 최대공약수로 나눈 것이다.
최대공약수는 유클리드 호세법을 사용하여 간단하게 구해낼 수 있다.
유클리드 호세법에 관련된 문제가 직전에 있었는데 백준 2609번 필자 풀이를 참고해주시면 된다.
현재 문제랑 똑같은 문제다.