[알고리즘] 최대 공약수와 최소 공배수

최대 공약수 (Greatest Common Divisor, GCD)

• 두 자연수의 공통된 약수 중 가장 큰 공약수를 최대 공약수라 한다.
  8의 약수 1 2 4 8
  12의 약수 1 2 3 4 6 12
  공통된 약수 1 2 4
  최대 공약수 4

유클리드 호제법

• 유클리드 호제법은 a>b일때 a, b를 나눈 나머지를 r이라고 하면,
  r이 0일때 b가 최대 공약수가 되는 정리이다.
• 만약 r이 0이 아니라면, a에 b를 넣고 b에 n의 값을 넣고 n이 0이 될 때까지 반복하면 된다.
• a % b = r1
  b % r1 = r2
  r1 % r2 = r3
  ...
  r(n) % r(n+1) = 0
  최대 공약수는 r(n+1)
• 코드

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

최소 공배수 (Least Common Multiple, LCM)

• 두 자연수의 공통된 배수 중 가장 작은 공배수를 최소 공배수라 한다.
  8의 배수 8 16 24 32 40 48...
  12의 배수 12 24 36 48 ...
  공통된 배수 24, 48
  최소 공배수 24

공식

• 최소 공배수는 두 자연수의 곱 / 최대 공약수로 구할 수 있다.
• 코드

lcm = a * b / gcd(a, b);