최대공약수

유클리드 호제법에 대해 알아봅니다.

최대공약수

두 자연수 A, B에 대하여 A, B의 공통 약수 중 최댓값을 의미한다.

유클리드 호제법

2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘

호제법이라는 말은 두 수가 서로(호) 상대방 수를 나누어(제)서 결국 원하는 수를 얻는 알고리즘이다. 주요 성질은 다음과 같다.

• 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면 (단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

증명은 다음과 같이 할 수 있다.

코드

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