최대공약수 알고리즘

최대공약수란 두 수가 공통적으로 가진 약수 중에 제일 큰 정수를 말한다.

가장 많이 알려진 알려진 알고리즘은 유클리드 호제법을 사용해 구현하는 것이다.

유클리드 호제법이란?

두 수 A, B(A>B)에서 A를 B로 나눈 나머지가 r이면 GCD(A,B) = GCD(B,r)과 같고, r이 0일때 B가 최대공약수

유클리드 호제법의 논리를 재귀와 while문을 사용해 코드를 짤 수 있다.

1) 재귀로 구현

const GCD = (num1, num2) => {
  	if(num1 < num2) {
    	let temp = num1
        num1 = num2
      	num2 = temp
    }
	if(num2 === 0) return num1
  	return GCD(num2, num1 % num2)
}

2) while로 구현

const GCD = (num1, num2) => {
	if(num1 < num2) {
    	let temp = num1
        num1 = num2
      	num2 = temp
    }
  
  	while(true) {
        let r = num1 % num2
        if(r === 0) return num2
      	num1 = num2
      	num2 = r
    }
}

최소공배수 알고리즘

최소공배수는 두 수가 가지는 공통된 배수 중에서 제일 작은 정수를 말한다.

최소공배수(LCM) = (A * B) / 최대 공약수(GCD)

const LCM = (num1, num2) => {
	let gcd = GCD(num1, num2)
    return (num1 *num2) / gcd
}