프로그래머스 1단계 - 최대공약수와 최소공배수

프로그래머스 1단계 - 최대공약수와 최소공배수

🍞 문제 설명

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

---

🍞 제한 조건

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

---

🍞 입출력 예

n	m	return
3	12	[3, 12]
2	5	[1, 10]

입출력 예 #1
위의 설명과 같습니다.

입출력 예 #2
자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.

---

🍞 문제 풀이

모르겠어서 풀이법을 찾아보았습니다.
이 방법은 유클리드 호제법이라고 하며 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나라고 합니다.
호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타냅니다.

function solution(n, m) {
  let min = (n < m) ? n : m;
  let rag = 0;
  for (let i = 1; i <= min; i++) {
      if (n % i == 0 && m % i == 0)
          rag = i;
  }
  return answer = [rag, n * m / rag]
}

---

🍞 다른 이의 풀이

for문을 통해 반복하며 최대공약수와 최소공배수를 구하는 방법입니다. 두 수 중 작은 수를 먼저 구해야 한다는 점은 위와 같네요.

function solution(n, m) {
  const min = Math.min(n, m);
  let common_max = 1;
  for(let i = min; i > 0; i--){
      if(n % i === 0 && m % i === 0){
          common_max = i;
          break;
      }
  }
  return [common_max, common_max * (n / common_max)* (m / common_max)];
}

문제 풀어보기