BackJoon - 2609

Lucky Unlucky·2025년 7월 7일
0

Backjoon 문제풀기

목록 보기
22/29

문제


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


입력


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


출력


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


예제



해결


const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split(" ").map((item) => Number(item));

let a = input[0];
let b = input[1];

while(a % b !== 0){
    let r = a % b;
    
       if(r !== 0){
        a = b;
        b = r;
    }
}
console.log(b);
console.log((input[0] * input[1]) / b);

유클리드 호제법으로 구하는 문제입니다.
유클리드 호제법에 대한 내용은 해당링크에 정리되어 있습니다.
https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

while (a % b !== 0) {
    let r = a % b;
    if (r !== 0) {
        a = b;
        b = r;
    }
}

a % b가 0이 아닐 동안(while (a % b !== 0)) 반복해서:
r = a % b 로 나머지를 구하고
그 나머지(r)가 0이 아니면 a <- b, b <- r 로 값을 갱신합니다.

console.log(b);
console.log((input[0] * input[1]) / b);

반복이 끝난 시점의 b를 출력합니다. 이 값이 바로 최대공약수입니다.

두 수의 곱을 최대공약수로 나오면 최소공배수가 나오므로
console.log((input[0] * input[1]) / b); 를 출력해줍니다.

profile
늒네입니다.

0개의 댓글