[JS] 최대공약수(GCD) & 최소공배수(LCM) 구현하기

최대공약수(GCD)

• 두 수 A와 B의 공약수 중에 가장 큰 정수

기본적인 코드

• 2부터 min(A,B)까지 모든 정수로 나누는 방법

let getGCD = (num1, num2) => {
    let gcd = 1;

    for(let i=2; i<=Math.min(num1, num2); i++){
        if(num1 % i === 0 && num2 % i === 0){
            gcd = i;
        }
    }

    return gcd;
}

최소공배수(LCM)

• 두 수 A와 B의 공배수 중 가장 작은 정수

기본적인 코드

• 1부터 더해가며 나머지값이 0인걸 확인하는 방법

let getLCM = (num1, num2) =>{
	let lcm = 1;
   
    while(true){
      if((lcm % num1 == 0) && (lcm % num2 == 0)){
        break;
      }
      lcm++;
    }
  	return lcm
}

유클리드 호제법 이용

• num1를 num2로 나눈 나머지를 r이라고 했을 때, GCD(num1, num2) = GCD(num2, r) 원리 이용

재귀

let getGCD = (num1, num2) => (num2 > 0 ? getGCD(num2, num1 % num2) : num1);

while문

let getGCD2 = (num1, num2) => {
  
    while(num2 > 0){
        let r = num1 % num2;
        num1 = num2;
        num2 = r;
    } 

    return num1;
}

최소공배수

function solution(num1, num2) {
    const gcd = (a, b) => a % b === 0 ? b : gcd(b, a % b);
    const lcm = (a, b) => a * b / gcd(a, b);
    return [gcd(num1, num2), lcm(num1, num2)];
}

✅ 프로그래머스 문제 - 숫자카드 나누기

https://school.programmers.co.kr/learn/courses/30/lessons/135807

function solution(arrayA, arrayB) {
  function gcd(n1, n2) {
    return n1 % n2 === 0 ? n2 : gcd(n2, n1 % n2);
  }
  function tmp(arrayA, arrayB) {
    let gcdA = 0;
    arrayA.sort((a, b) => a - b);
    arrayA.forEach((A) => (gcdA = gcd(gcdA, A)));
    if (arrayB.some((B) => B % gcdA === 0)) return 0;
    return gcdA;
  }
  let A = tmp(arrayA, arrayB);
  let B = tmp(arrayB, arrayA);
  return Math.max(A, B);
}