[프로그래머스 1단계] 최대공약수와 최소공배수 구하기_유클리드 호제법

문제설명

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

 

주의사항

• 두 수는 1이상 1000000이하의 자연수입니다.

입출력예시

코드

function solution(n, m) {
    return [ gcd(n,m), (n*m) / gcd(n,m)]
}

function gcd(a, b) { // 단, a가 b보다 커야함.
        let R;
        while ((a % b) > 0)  {
             R = a % b; //나머지
                a = b;
                b = R;
        }
         return b;
        }

 

해석

// 최대 공약수 : 유클리드 호제법
// 최소 공배수 : input으로 주어진 자연수 2개를 곱하고 최대 공약수로 나누는 방식으로 구해야 한다고 한다.

 

유클리드 호제법이란? 2개의 자연수 또는 정식의 최대공약수(Greatest Common Divisor)를 구하는 알고리즘의 하나이다.

호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다.

2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다

function gcd(a, b) { // 단, a가 b보다 커야함.
  let R;
  while ((a % b) > 0)  {
    R = a % b;
    a = b;
    b = R;
  }
  return b;
}

 

한줄평

이 문제를 통해 유클리드 호제법을 알고 최대공약수와 최소공배수를 어떻게 구하는지 배웠다.

좋은 문제 감사합니다.

 

링크

https://programmers.co.kr/learn/courses/30/lessons/12940

유클리드 호제법 : https://seunghyum.github.io/algorithm/Euclidean-algorithm/#