기초 알고리즘 1/2. 300 - 수학 1
2609번. 최대공약수와 최소공배수

문제

2609번 문제 링크

solution

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];

// 유클리드 호제법
// (a,b) = (b,r). a와 b라는 자연수를 나눈 나머지가 r이다.
// r이 0이 되는 순간까지 반복한다. 그 때의 b가 최대공약수이다.
while(a % b !== 0){
    let r = a % b;
    
    // r이 0이 아니라면, a자리에 b를 넣고, b자리에 r을 넣는다.
    if(r !== 0){
        a = b;
        b = r;
    }
}

// 최대공약수
console.log(b);

// 최소공배수
// 두 자연수의 곱을 최대공약수로 나누면 최소공배수를 구할 수 있다.
console.log((input[0] * input[1]) / b);

예시를 보면 쉽게 이해할 수 있다.

input = [24, 18]

1. 최대공약수 구하기
유클리드 호제법 : (a, b) => (b, r), r은 a % b

(a, b) = (24, 18) => (18, 6) => (6, 0)

r이 0이 되었으므로, 그 때의 b가 최대공약수이다.
여기서 a라고 혼동할 수도 있는데,
r이 0이 되었을 때는 if문이 실행되지 않으므로, a에 b가 들어가지 않아서
b를 출력해아지 알맞게 출력한 것이다.

2. 최소공배수 구하기
최소공배수 = (자연수1 * 자연수2) / 두 자연수의 최대공약수

참고 자료

참고 자료 1
유클리드 호제법 위키백과