[Math&Algorithm] 최대공약수? 최대공배수?

▷최대공약수란?

: GCD(Greatest Common Divisor)

: 두 수 A와 B의 공통된 약수 중에서 가장 큰 정수

 

▷구하는 방법?

① 2부터 min(A, B)까지 모든 정수로 나눠서 나머지가 0이 되는 최대 정수 찾기.

② 유클리드 호제법(Euclidean algorithm)으로 찾기.

    : a를 b로 나눈 나머지를 r 이라고 했을 때, GCD(a, b) = GCD(b, r) 이 성립한다. → 재귀로 구현 가능

    : r이 0이면 그 때의 b가 최대 공약수 이다.

    ex) GCD(16, 12) = GCD(12, 4) = GCD(4, 0) = 4 → GCD(a, b) = GCD(b, a%b) 로 표현 됨

 

▷최대공배수란?

: LCM(Least Common Multiple)

: 두 수의 공통된 배수 중에서 가장 작은 정수

 

▷구하는 방법?

: 최소공약수 g를 알 때, g * (a/g) * (b/g) 로 구할 수 있다.