[Algorithm] GCD / LCM

1251 단어 algorithmalgorithm

Greatest Common Divisor(최대공약수)


유클리드 호제법(Euclidean Algorithm) - O(log N)

function GCD(m, n) {
  if (m % n == 0) return n;
  return GCD(n, m % n);
}

r = m % n 일 때
(m, n)GCD == (n, r)GCD라는 성질을 이용한 최대공약수 공식

Least Common Multiple(최소공배수)


LCM = (M * N) / GCD

좋은 웹페이지 즐겨찾기