자바스크립트 최대공약수와최소공배수

// 최대공약수와 최소공배수
// 어떤수를 나누어떨어지게 하는 수(나누었을때 나머지가 없음)  : 약수
//  12 의 약수 : 1 2 3 4 6 12  18의약수 : 1 2 3 6 9 18
//최대공약수 : 두수의 공약수인 1 2 3 6 이중 최대값인  6
// 최소공배수 : 두수의 공약수인 1 2 3 6 을 곱한 값   1*2*3*6 = 36


function solution(n, m) {
    let gcd = 1;
    // 최대공약수
    for ( i= 1 ; i<=Math.min(n,m); i++){

        if(n%i === 0 && m%i === 0 ){
            gcd = i;
        }
    }

    // 최소공배수
        //   216      =   12 *  18    
    // 두수의 곱 = 최대공약수 * 최소공배수
    // 최소공배수 = 두수의곱/최대공약수
    let lcm = n*m/gcd;
    
    console.log(gcd)
    console.log(n*m/gcd)

    return [gcd ,lcm];

}
console.log(solution(3,12))
// 유클리드 호제법을 이용한 풀이 

// - a,b 를 서로 나눌때, 나누어진다면 b가 최대 공약수 이다. (a>b)

// - 만약 a,b가 나누어지지 않으면 b와 a를 b로 나눈 나머지를 다시 나눈다

// - 서로가 나누어지면 a%b 가 최대공약수이다.

// 나누어지지 않는다면 위처럼 b와 a를 b를 나눈 나머지를 다시 나눈다.