[알고리즘] 유클리드 호제법 #c언어

[유클리드 호제법]

유클리드 호제법 : 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나.

- 명시적으로 기술된 가장 오래된 알고리즘으로 알려져있다.

- 기원전 300년경에 쓰인 유클리드의 <원론> 제 7권, 명제 1부터 3까지에 해당

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

알고리즘

- 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하자 (단, a > b)

- a와 b의 최대 공약수는 b와 r의 최대공약수와 같다.

- 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복

- 이때 나머지가 0이 된다면 나누는 수가 a와 b의 최대공약수이다.

[알고리즘]

- 입력으로 두 수 m, n(m>n)을 입력받는다.

- n이 0이라면, m을 출력하고 알고리즘을 종료

- m이 n으로 나누어 떨어지면, n을 출력하고 알고리즘을 종료

- 그렇지 않으면, m을 n으로 나눈 나머지를 새롭게 m에 대입하고, m과 n을 바꾸고 3번으로 돌아온다.

[c언어]

int gcd(int a, int b) {
    return b ? gcd(b, a%b) : a;
}

int gcd(int a, int b) {
       int c;
       while(b) {
            c = a % b;
            a = b;
            b = c;
       }
       return a;
}