최대 공약수는 두 수 이상의 수에 대한 공약수(공통된 약수) 중에서 가장 큰 수를 가리킵니다. GCM(Greatest Common Measure) 또는 GCD(Greatest Common Divisor)이라고 표기하기도 합니다.

이 방법은 '유클리드 호제법 (互除法, Euclidean algorithm)'을 응용하여 두 정수간의 최대공약수를 구하는 코드구현입니다.

• 두 양의 정수 a와 b (단, a > b 일 때)에 대하여 a = bq + r (단, 0 ≤ r ≤ b) 또는 a ≡ r (r은 a mod b) 이라 하면, a와 b의 최대공약수 b와 r의 최대공약수와 같다.
  • 즉, gcd(a, b) = gcd(b, r) 에서 r 이 0이라면, a와 b의 최대공약수는 b가 된다.
• 여기서 '호제법'이라는 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘(algorithm)을 의미합니다.
• 간단히 이것을 C언어 함수로 핵심적인 요점만 구현한다면 다음과 같은 구현을 의미합니다.
  
  

gcm.c 로 소스를 저장후 컴파일은 요렇게 합니다.

[백점맞는수학] 초등5학년_공약수와최대공약수

참고 영상

[Youtube movie]

[재미있는수학 Funny Math] 최대공약수 구할때 소인수분해 하지마세요 (재미있는 수학 유클리드 호제법)

참고 영상

[Youtube movie]