최대공약수와 최소공배수

Posted on Edited on In Word count in article: 233 Reading time ≈ 1 mins.

문제

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

제한사항

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

풀이방향

  • 두 수의 최대공약수 구하기
  • 두 수의 최소공배수 구하기

입출력 예

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

풀이

greatestCommonDivisor.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function greatestCommonDenominator(n, m) {
  let answer = [];
  let divisor = getCommonDivisor(n, m);
  let minCommonMultiple = getMinCommonMultiple(n, m);
  answer.push(divisor);
  answer.push(minCommonMultiple);
  return answer;
}

function getCommonDivisor(n, m) {
  //common divisor
  let divisor = 1;
  for (let i = 1; i <= n && i <= m; i++) {
    if (n % i === 0 && m % i === 0) {
      divisor = i;
    }
  }
  return divisor;
}

function getMinCommonMultiple(n, m) {
  //common multiple
  let divisor = getCommonDivisor(n, m);
  return (n * m) / divisor;
}

export { greatestCommonDenominator };
greatestCommonDivisor.test.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import { greatestCommonDivisor } from '../src/greatestCommonDivisor.js';

describe("greatestCommonDivisor", () => {
  it("should return a divisor and a minCommonMultiple", () => {
    const answer = greatestCommonDivisor(3, 12);
    expect(answer[0]).toBe(3);
    expect(answer[1]).toBe(12);
  });

  it("should return a divisor and a minCommonMultiple", () => {
    const answer = greatestCommonDivisor(2, 5);
    expect(answer[0]).toBe(1);
    expect(answer[1]).toBe(10);
  });
});

출처

  • 프로그래머스

다른 풀이

1
2
3
4
5
function greatestCommonDivisor(a, b) {return b ? greatestCommonDivisor(b, a % b) : Math.abs(a);}
function leastCommonMultipleOfTwo(a, b) {return (a * b) / greatestCommonDivisor(a, b);}
function gcdlcm(a, b) {
    return [greatestCommonDivisor(a, b),leastCommonMultipleOfTwo(a, b)];
}