[자바스크립트] 2609 최대공약수와 최소공배수

2609번: 최대공약수와 최소공배수

문제

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

 

 

입력

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

 

 

출력

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

 

 

예제 입력 1

24 18

 

 

예제 출력 1

6
72

 

 

자료구조

① 정수: a, b, gcd(a,b), lcm

 

 

알고리즘

① 최대공약수(GCD) 계산 : 

두 숫자의 최대공약수를 유클리드 호제법을 통해 계산합니다.

1. 두 숫자 a와 b의 나머지를 반복적으로 계산합니다.
2. 나머지가 0이 될 때까지 이 과정을 반복합니다.
3. 나머지가 0이 되는 시점의 a 값이 두 숫자의 최대공약수(GCD)가 됩니다.

예시:

• gcd(24, 36)의 과정:
  1. 36 % 24 = 12
  2. 24 % 12 = 0
  3. GCD는 12

② 최소공배수(LCM) 계산 : 

최소공배수(LCM)는 두 숫자 a와 b의 곱을 최대공약수(GCD)로 나누어 계산합니다.

예시:

• lcm(24, 36)의 과정:
  1. 24 * 36 = 864
  2. 864 / 12 (GCD) = 72
  3. LCM은 72

 

 

소스 코드 

let fs = require("fs");
let [a, b] = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split(" ")
  .map(Number);

function gcd(a, b) {
  while (b !== 0) {
    let temp = b;
    b = a % b;
    a = temp;
  }

  return a;
}

console.log(gcd(a, b));

const lcm = (a * b) / gcd(a, b);
console.log(lcm);코드

96ms

 

 

 

✔ 출처

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