[백준] 2609번 최대공약수와 최소공배수

유클리드 호제법

1. 먼저 두개의 수를 서로 나눈 나머지를 구한다. ex) 1071 % 1029 = 42

2. 두 수 중 작은 수를 다시 나머지로 나눈다. ex) 1029 % 42 = 21

3. 나누어 떨어질때까지 반복한다.

4. 나누어떨어지면 나눈 수가 최대공약수가 된다. ex) 42 % 21 = 0 최대공약수는 21

최소공배수 = A X B / 최대공약수

const input = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split(' ');

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

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

유클리드 호제법을 사용해서 간단하게 최대공약수를 구하는 방법을 알게 되었다.

Uploaded by Notion2Tistory v1.1.0