[백준 문제풀이] 2609번 최대공약수와 최소공배수

2609번 최대공약수와 최소공배수 (Bronze 1)

문제

https://www.acmicpc.net/problem/2609

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

입력

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

출력

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

풀이

오늘은 알고리즘 문제에 집중이 되지 않아서, 자꾸 에러가 나고 코드가 예쁘지가 않아 최소공배수와 최대공약수의 개념을 찾아보았다.

최소공배수를 구하는 방법으로 신기한 것을 알 수 있었는데 gcd : 최대공약수, lcm : 최소공배수 a _ b = gcd _ lcm이라는 식을 통해서 lcm = (a*b) / gcd를 통해 구할 수 있다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split(" ");
input = input.map((el) => parseInt(el));

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

if (a < b) {
  let a = input[1];
  let b = input[0];
}

let gcd = 1;

for (let i = 2; i <= b; i++) {
  if (a % i === 0 && b % i === 0) {
    gcd = i;
  }
}

const lcm = (a * b) / gcd;

console.log(gcd);
console.log(lcm);