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

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

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

 

✅문제

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

✅입력

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

 

✅출력

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

 

💬입력 예시

24 18

💬출력 예시

6
72

---

🍀제출 및 설명

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

let num1 = Number(input[0]);
let num2 = Number(input[1]);

let gcd = 1;

for(let i=2;i<=Math.min(num1,num2);i++){
    if(num1%i===0&&num2%i===0){
        gcd = i;
    }
}

let lcm = num1*num2/gcd
console.log(gcd)
console.log(lcm)

두수를 num1, num2에 할당합니다.

최대공약수를 구하려고 합니다.

최대 공약수는 두수중 작은 수 보다 크지 않고, 두수를 나눴을 경우 나누어 떨어지는 가장 큰 수 입니다.

여기서 1은 모든 수를 나눌수 있기때문에 가장 작은 값을 2로 설정해

for문을 만들고, 해당 조건에 부합하는 if문을 만들었습니다.

 

최소공배수는 두수의 곱에 최대공약수를 나눈 값이기 때문에 let lcm = num1*num2/gcd로 구했습니다

 

✨다른 풀이

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().split(' ');

input = input.map((el)=> +el)//.split(' ')

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

// 유클리드 호제법으로 최대공약수와 최소 공배수 구하기
function solution(a, b) {
  let greatest = (a, b) => a % b === 0 ? b : greatest(b, a % b);
  let least = (a, b) => a * b / greatest(a, b);

  console.log(greatest(a, b), least(a, b));
}
  
solution(a, b);

해당 문제를 담당하여 설명해주신 스터디원분의 코드가 좋아서 가져왔습니다.

 

최대공약수를 구한 방법이 독특한데 유클리드 호제법을 사용했다고 합니다.

 

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 이는 명시적으로 기술된 가장 오래된 알고리즘으로서도 알려져 있으며, 기원전 300년경에 쓰인 유클리드의 《원론》 제7권, 명제 1부터 3까지에 해당한다.
(아래 블로그 참조)

쉽게 큰수에서 작은수를 나눴을 경우 0이 나오면 작은수가 최대 공약수이고,

나머지가 나온 경우 작은수에서 나머지를 나눈다 0이 나오는 경우 이전에 나온 나머지가 최대공약수이고,

또 나머지가 나온경우 해당 행동을 반복해 나머지가 0이 나올때까지 한다. 

 

이중 반복되는 부분을 제귀로 처리하여 식을 간단하게 만들었다.

 

또 다음은 solution에 a,b의 대소비교가 없어서 오류가 발생할수 있는데, 다음을 a>b?solution(a,b):solution(b,a)로 하여 solution함수가 시작되기 전부터 대소비교를 끝내고 들어가는 방법을 사용하셨다.

---

 

🐾알고리즘

• 수학
• 정수론
• 유클리드 호제법

 

🐾참조

https://tech.lonpeach.com/2017/11/12/Euclidean-algorithm/

유클리드 호제법이란? | Lonpeach Tech