최대공약수와 최소공배수

문제

두 개의 정수가 주어졌을 때, 이들의 최대공약수와 최소공배수를 찾는 함수를 작성하세요.

나의 풀이

function greatestCommonDenominator(num1, num2) {
    let min1 = [];
    let min2 = [];
    let commonDenominator = [];

    for (let i = 1; i <= num1; i++) {
        if (num1 % i == 0) {
            min1.push(i);
        }
    }

    for (let j = 1; j <= num2; j++) {
        if (num2 % j == 0) {
            min2.push(j);
        }
    }

    for (let i = 0; i < Math.max(min1.length, min2.length); i++) {
        if (min2.includes(min1[i])) {
            commonDenominator.push(min1[i]);
        }
    }
    console.log(Math.max(...commonDenominator));

}

greatestCommonDenominator(12, 6);

 

다른 풀이1

function greatestCommonDivisor(num1, num2) {
    let gcd;
    for (let divisor = Math.min(num1, num2); divisor >= 1; divisor--) {
        if (num1 % divisor === 0 && num2 % divisor === 0) {
            gcd = divisor;
            break;
        }
    }
    return gcd;
  }
  console.log(greatestCommonDivisor(12,6));

 

다른 풀이2

- 유클리드 호제법 참고

function gcdAndlcm(a, b) {
    const gcdValue = gcd(a, b);
    const lcmValue = (a * b) / gcdValue;
    return { gcd: gcdValue, lcm: lcmValue };
  }
  function gcd(a, b) {
    if (b === 0) {
      return a;
    } else {
      return gcd(b, a % b);
    }
  }
  console.log(gcdAndlcm(8, 12));