최대공약수와 최소공배수

문제

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, 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)];
}