JavaScript - 최대공약수, 최소공배수

최대공약수 (the greatest common denominator)

JS로 두 수의 최대공약수 구하기!

일단 최대공약수가 뭔지 다들 아시겠지만, 최대공약수는 사전적인 의미로 '둘 이상의 정수(整數)의 공약수 가운데 가장 큰 수. 정식(整式)에서는 공약수 가운데 차수가 가장 높은 것을 이른다' 인데 그림으로 설명하는 것이 더 이해가 빠르겠네요.... 한국어 너무 어려워요 ㅠ

84와 120의 최대공약수는 2*2*3인 12입니다! 저렇게 소수를 나누다보면 나오게 됩니다.

그것을 JS로 만들어보면 됩니다.

 

두 수를 나눴을 때 둘 다 나머지가 0이 나오는 수를 찾으면 되겠죠!

 

let GCD = (num1, num2) => {
    let gcd = 1;

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

    return gcd;
}

for 문으로 2부터 두 수중에 작은 숫자까지 반복문을 돌리면서 나누면서 i인 숫자로 나눴을 때 두 숫자 모두 나머지가 0인 것을 최대공약수로 한다 라는 문장을 만들었습니다.

하지만 이 세상은 더 짧고 완벽한 식을 원합니다.

그래서 유클리드 호제법을 이용하여 구현을 해보았습니다.

 

유클리드 호제법을 이용한 최대공약수 구하기

유클리드 호제법에 대한 정의를 보여주는 링크입니다. 확인해보세요! 저는 가볍게 집고 넘어갈게요.

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

위에 84, 120을 예로 들면

GCD(84,120) => GCD(120,84) => GCD(84,36) => GCD(36,12) => GCD(12,0) => 최대공약수 = 12

 

이렇게 구하게 됩니다.

let GCD = (num1, num2) => (num2 > 0 ? GCD(num2, num1 % num2) : num1);

** 혹시나 저처럼 왜! 화살표 함수에 {}중괄호가 안들어가고 ()소괄호가 들어갔는지 모르는 분들을 위해 알려드립니다. return이라는 명령어를 생략하기 위해서 ()소괄호를 사용해서 문장을 만들었습니다. 물론, 아예 아무것도 안사용하거나 중괄호에 return 을 넣어서 사용하면 됩니다.

 

이런 함수를 만들거나 while문을 사용해서도 만들 수 있습니다.

let GCD2 = (num1, num2) => {
  
    while(num2 > 0){
        let r = num1 % num2;
        num1 = num2;
        num2 = r;
    } 

    return num1;
}

 

그렇다면 두수의 최소공배수는 어떻게 구하면 될까요?

최소공배수 구하기

두수의 최소공배수는 두수를 곱하고 최대공약수로 나누어주면 끝납니다! 너무 간단하죠

그렇기 때문에 따로 뭘 하지 않아도 됩니다. 구해놓은 최대공약수로 두수의 곱을 나누어주면 되기 때문이죠. ㅎㅎ

그 이유는 위에 그림을 보고 직접 수식을 짜보시면 됩니다.

 

세상에는 알고 있는 것도 더 쉽게 배울 수 있게 만들어주는 그런... 것들이 많네요. 어릴 때부터 검색하는 습관을 길러왔다면 손쉽고 재미난 세상에 살았을 텐데 그때는 궁금한 것이 별로 없던 시절이었습니다.

하지만 뭐 어떻습니까 지금 현재가 중요하고 계속 해서 모르는 것을 뇌에 채우는 즐거움을 가져보아요~

---

참고 자료 

https://velog.io/@devjade/JavaScript%EB%A1%9C-%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98GCD-%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98LCM-%EA%B5%AC%ED%95%98%EA%B8%B0

 

JavaScript로 최대공약수(GCD), 최소공배수(LCM) 구하기