[유용한 JS 정보] 최대공약수, 최소공배수

코딩하며 유용한 정보가 생각날 때마다 작성하는 글입니다.

최근 프로그래머스라는 코딩 관련 사이트에서 여러 코딩 문제들을 풀면서 많은 함수들의 사용 방법과 여러 공식들을 배우고 공부했습니다!

이번에는 자바스크립트로 최대공약수와 최소공배수를 구하는 방법을 소개하겠습니다.

유클리트 호제법

유클리드 호제법의 기본 원리는 num1를 num2로 나눈 나머지를 r이라고 했을 때, GCD(num1, num2) = GCD(num2, r)과 같다는 것입니다.

최대공약수(GCD)

function getGCD(num1, num2) {
	while (num2 !== 0) {
    	let r = num1 % num2;
      	num1 = num2;
      	num2 = r;
    }
  	return num1;
}

최소공배수는 최대공약수를 구하는 코드를 활용하면 쉽게 구할 수 있습니다.

최소공배수(LCM)

function getLCM(num1, num2) {
	return num1 * num2 / getGCD(num1, num2);
}