1. 유클리드 호제법이란

두 수의 최대공약수를 구하는 알고리즘입니다.

• 호제법 : 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘.

2. 유클리드 호제법 예시

EX)

1. 일반적인 방법

1112 = 139 X 2 X 2 X 2
695 = 139 X 5

2. 유클리드 호제법

MOD연산 이용!
MOD연산 : 두 값을 나눈 나머지를 구하는 연산! (%)

1112 % 695 = 417
695 % 417 = 278
417 % 278 = 139
278 % 139 = 0
나머지가 0이 됐을 때, 마지막 계산에서 나누는 수로 사용된 139가 1112와 695의 최대공약수가 된다!

3. 코드

1. 반복문으로 풀기

int GCD(int a, int b){
  int tmp;
  while(b){      //b가 0이 될 때까지
    tmp = a % b;
    a = b;
    b = tmp;
  }
  return a;
}

1. a%b 를 tmp에 저장해줍니다.
2. 나누어질 수 a에 전에 나눈 수 b를 저장합니다.
3. 나눌 수 b에 전에 나눈 나머지 tmp를 저장합니다

2. 재귀함수로 풀기

int divide(int x, int y)
{
    if (x % y == 0)
        return y;
    else
        return divide(y, x % y);
}

1. %로 나눈 값이 0이면 최대공약수 y 리턴합니다.
2. 아니면 함수호출 리턴합니다.