[BOJ]1934 - 최소공배수(JS)

 

풀이

let fs = require("fs");
let input = fs.readFileSync('예제.txt').toString().trim().split("\n").map(a=>a.split(" ").map(Number))
answer = [];
input = input.splice(1,input.length)

for(let i = 0; i < input.length ; i++){
    let [a,b] = input[i]
    console.log(a,b)
    let oriA = a;
    let oriB = b;
    
    while( a % b !== 0 ){
        let r = a % b;
        if(r!== 0){
            a=b
            b=r
        }
    }
    let min = oriA * oriB / b;
    answer.push(min)
}
console.log(answer.join("\n"))

 

유클리드 호제법 :

 

• • 유클리드 알고리즘은 두 수의 최대공약수(GCD)를 구하는 효율적인 방법입니다.
  • 두 수 a와 b가 주어지면, a를 b로 나눈 나머지를 r로 설정하고, a를 b로, b를 r로 교체합니다. 이 과정을 b가 0이 될 때까지 반복하면, 최종적으로 a가 GCD가 됩니다.

원래 두 수의 곱을 최대 공약수로 나누면 최소공배수가 나옴.