[알고리즘] 최대 공약수, 최소 공배수 찾기 (유클리드 호제법)

🔎 나의 풀이

function solution(n, m) {
    let gcf = 0; // 최대공약수 Greatest Common Factor
    let lcm = 0; // 최소공배수 Least Common Multiple
    let multipleN = [] // n의 배수
    let multipleM = [] // m의 배수

    // 최소공배수
    for (let i = 1; i <= Math.max(n, m); i++) {
        multipleN.push(n*i)
        multipleM.push(m*i)
    }
     lcm = multipleN.filter(el => multipleM.includes(el))

  // 최대공약수
  for (let j = 1; j <= Math.max(n, m); j++) {
    if (n % j === 0 && m % j === 0) {
      gcf = j
    }
  }
    return [gcf, lcm[0]]
}

💡 유클리드 호제법 ?

🔎 유클리드 호제법을 이용한 풀이

function solution(n, m) {
    
    const gcd = (n, m) => {
      return (n % m === 0) ? m : gcd(m, n % m)
    }
    
    const lcm = (n, m) => {
      return n * m / gcd(n, m)
    }
    
    return [gcd(n, m), lcm(n, m)]
}