유클리드호제법(최대공약수 구하기)+최소공배수 > feat. BOJ 2609

정의

유클리드 호제법(- 互除法, Euclidean Algorithm)은 2개의 자연수 또는 정식(整式)의 최대공약수(Greatest Common Divisor)를 구하는 알고리즘의 하나이다.
호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다.
2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.
이는 명시적으로 기술된 가장 오래된 알고리즘으로서도 알려져 있으며, 기원전 300년경에 쓰인 유클리드의 《원론》 제7권, 명제 1부터 3까지에 해당한다.
-위키백과, 우리 모두의 백과사전.

거두절미하고 예시로 보는게 최고다..

78696(a) ＝ 19332(b)×4 ＋ 1368(a%b)
19332(a) ＝ 1368(b)×14 ＋ 180(a%b)
 1368 ＝ 180×7 ＋ 108
  180 ＝ 108×1 + 72
  108 ＝ 72×1 ＋ 36
   72 ＝ 36×2 >> 나머지가 0이 되었을 때 나누는 수가 최대공약수

BOJ 알고리즘 문제 2609

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

const fs = require('fs');
 const stdin = (
   process.platform === 'linux'
     ? fs.readFileSync('/dev/stdin').toString()
     :`24 18`).trim().split(' ');

let a = stdin[0]
let b = stdin[1]

//위의 예시처럼 a를 b로 나눴을 때 나머지가 0이 아닐 경우 extra에 나머지 값을 넣어두고 a는 b로 b는 이 나머지 값을 다시 바꿔서 반복문을 돌리다가 else(=나머지가 0일 때 b의 값을 최대공약수로 바꾼다.
while (a%b!== 0) {
  let extra = a%b;
  if(a%b!==0) {
    a=b
    b=extra
  } else {
    b=extra
    break
  }
}

let min = (stdin[0]*stdin[1])/b
console.log(b)
console.log(min)

최소공배수

(a*b)/최대공약수