최소공배수와 최대공약수의 관계

• n = a * b 일떄, a 와 b 는 n 의 약수이다.

• a <= b 라고 하면, a 의 최대값은 b 가되어 n = b * b 가 될 수 있다. 이것은 소수를 구할때 유용한 특징으로 사용된다.

• a 와 b 의 최소 공약수를 G = gcd(a, b) 라고 하면,

  Greatest Common Denominator

• a = Gx, b = Gy 인 x, y 쌍이 존재한다.
• 이때, a*b = GGxy 이며, x, y 는 서로소이다. 집합 관계로 생각해볼때, a 와 b 의 최소공배수는 Gxy 가 된다.
• 따라서 최소공배수 L = lcm(a, b) = Gxy = (ab)/G = (ab)/gcd(a, b) 가 성립한다.

  Least Common Multiple

• 두 수의 최소공배수는 최대공약수를 알 수 있으면, 함께 알 게 된다.

최대공약수 구하기

간단히 생각해 보았을때, Brute Force 방법으로 O(n^2) 의 시간복잡도로 풀 수 있다.

• 2부터 a 와 b 중 작은수까지 루프를 돌며 a, b 둘다 나눠 떨어지는 수 구하기
• 반대로 a 와 b 작은 수 부터 2 까지 루프를 돌며 a, b 둘다 나눠 떨어지는 수 구하기

위의 방법을 유클리드 호제법을 사용하면 O(n^2) 의 벽을 뚫을 수 있다.

유클리드 호제법

• f(a, b) = gcd(a, b) 일때,
• a%b = 0 이면, f(a, b) = gcd(a, b) = b 이다.

  a >= b 일 경우

• 이떄, a%b != 0 이면, f(a, b) = gcd(a, a%b) 이다. « 이게 유클리드 호제법.

  증명은 다른데가서 보세요 ㅠㅠ 머절이는 그냥 외우겠읍니다…

• 예를 들어, a=18, b=12 라고 하면,
• 18%12 = 6, 0 이 아니므로, 18%6 = 0, 0 이므로 6이 최대공약수.

  할 때마다 신기하다.

유클리드 호제법은 O(log2(min(a, b))) 의 시간 복잡도를 가진 알고리즘이다.

끝.

참고

• 최대 공약수와 공배수를 구하는 알고리즘 (feat. 유클리드 호제법)