수학 알고리즘 - 최대 공약수(GCD) 알고리즘(유클리드 호제법)

최대 공약수 개요

최대 공약수는 두 개 이상의 정수를 나누어 떨어지게 하는 가장 큰 양의 정수를 말합니다.

예를 들어, 12와 18의 최대 공약수는 6입니다.

 

소인수 분해를 이용한 최대 공약수 동작원리

1. 두 수를 소인수분해합니다.
2. 공통된 소인수들을 찾아냅니다.
3. 공통된 소인수들의 곱이 최대 공약수입니다.

소인수 분해를 이용한 최대 공약수 코드 예시

// 소인수 구하기
function getPrimeFactors(n) {
 const factors = []
 let divisor = 2
 
 while(n >= 2) {
  if(n % divisor === 0) {
   factors.push(n)
   n /= divisor
  } else {
   divisor++
  }
 }
}

// 최대공약수 구하기
function gcd(a, b) {
 let primeFactorsA = getPrimeFactors(a)
 let primeFactorsB = getPrimeFactors(b)
 
 if(primeFactorsA.length > primeFactorsB.length) {
  [primeFactorsA, primeFactorsB] = [primeFactorsB, primeFactorsA]
 }
 
 return primeFactorsA
  .filter((factor) => {
   	const factorIdx = primeFactorsB.indexOf(factor)
    if (factorIdx !== -1) {
     primeFactorsB.splice(factorIdx, 1)
     return true
    }
    return false
  })
  .reduce((acc,cur) => (acc *= cur))
}

길이가 작은 곳에서 길이가 많은 곳을 찾아야되기 때문에 길이가 앞에가 길면 배열을 바꿔줍니다.

공통된 소인수가 있으면 해당 소인수를 제거해주고 반환한뒤 반환된 모든 수를 곱해줍니다.

 

유클리드 호제법을 이용한 최대 공약수 동작원리

두 양의 정수 a,b(a > b)에 대하여 a = bq + r( 0 <= r < b)이라 하면, a,b의 최대 공약수는 b,r의 최대공약수와 같습니다.

gcd(a, b) = gcd(b, r)

r = 0이라면 a, b의 최대공약수는 b가 됩니다.

 

유클리드 호제법을 이용한 최대 공약수 코드 예시

function gcd(a, b) {
 if(a % b === 0) return b
 return gcd(b, a % b)
}

 

 

확장된 유클리즈 호제법을 이용한 최대 공약수 코드 예시

function extendEuclidean(r1, r2, s1, s2, t1, t2) {
 if(r2 === 0) return r1
 const q = parseInt(r1 / r2)
 const r = r1 - q * r2
 const s = s1 - q * s1
 const t = t1 - q * t2
 return extendEuclidean(r2,r, s2, s, t2, t)
}