알고리즘: 최대공약수(gcd)와 최소공배수(lcm)

문제 설명

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

제한 사항

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

입출력 예

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

풀이

최대공약수

두 수의 약수 중 가장 큰 수

• n1과 n2이상을 넘어갈 일이 없으므로 Math.min(n1,n2)까지로 범위 잡기
• n1과 n2를 동시에 나눌 수 있는 숫자(i)가 나타나면 return 하기 => 범위가 Math.min(n1, n2)이기 때문에 가능

최소공배수

두 수로 나눠질 수 있는 숫자 중 가장 작은 수

• n1과 n2로 동시에 나눠질 수 있는 수를 찾을 때까지 계속 1씩 증가시킴
• while문 사용하여 계속 돌리고 조건 만족했을 때 stop 시킴

const getGcd = (n1, n2)=> {
    let gcd = 1;
    for(let i = 2; i <= Math.min(n1, n2); i++) { 
        if((n1 % i === 0) && (n2 % i ===0)) gcd=i 
    }
    return gcd
}

const getLcm = (n1, n2)=> {
    let lcm = 1; 
    while(true) { // while문이 true이므로 계속 돌게 되어있음
        if((lcm % n1 ===0) && (lcm % n2 ===0)) break;//조건을 만족했을 때 스톱!
        lcm++
    }
    return lcm 
}

function solution(n, m) {
    let gcd = getGcd(n, m);
    let lcm = getLcm(n,m)
    
    return [gcd, lcm]
}