Lv.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 ] 을 리턴해야합니다. 

 

< 나의 풀이 > 

function gcd(a, b) {

    while( b !== 0){
        let temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

function lcm(a, b) {
    return (a * b) / gcd(a, b);
}

function solution(n, m) {
    return [gcd(n,m), lcm(n,m)];
}

 

• gcd(a,b) : 유클리드 호제법을 사용하여 두 수의 최대공약수를 구하는 함수로, 두 수가 주어지면 나머지가 0이 될 때까지 반복하여 최대공약수를 찾는다. 
• lcm(a,b) : 두 수의 최소공배수를 구하는 함수로, 최소공배수는 두 수의 곱을 최대공약수로 나눈 값으로 구할 수 있다. 
• solution(n,m) : 주어진 두 수 n, m의 최대공약수와 최소공배수를 계산하여 배열로 반환하는 함수이다.

유클리드 호제법

1. 두 수 a 와 b 의 최대공약수는 a 를 b로 나눈 나머지 r과 b의 최대공약수와 같다. ( gcd(a,b) = gcd(b,r) )
2. 나머지가 0이 될 때까지 이 과정을 반복한다.
3. 나머지가 0이 되었을 때의 b 값이 두 수 a와 b의 최대공약수이다.

ex ) gcd(48,18) 를 구해보자.

1. 48%18 = 12 ( r = 12 )  → gcd(48,18) = gcd(18,12)
2. 18%12 = 6 ( r = 6 )  → gcd(18,12) = gcd(12,6)
3. 12%6 = 0 ( r = 0 ) → gcd(12,6) = 6
4. gcd(48,18) = 6

< 다른 사람의 풀이 > 

function solution(a, b) {
    var r;
    for(var ab= a*b;r = a % b;a = b, b = r){}
    return [b, ab/b];
}

 

r : 나머지를 저장하는 변수 

ab = a*b : 나중에 최소공배수를 구하는 데 사용된다.

r = a%b : r 이 0이 되면 반복문이 종료된다.