[DS] Euclidean algorithm(유클리드 호제법) 과 최대 공약수

# 유클리드 호제법

- 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나

- 호제법이란?

  > 두 수가 서로 상대방 수를 나누어 원하는 수를 얻는 알고리즘을 나타냄

- 내용

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

  > a와 b의 최대공약수는 b와 r의 최대 공약수와 같음

  > 위의 성질에 의해 b를 r로 나눈 나머지 r'을 구하고 다시 r을 r'으로 나눈 나머지를 구하는 과정을 반복함

  > 위의 과정에서 나머지가 0이 될 때 나누는 수가 a와 b의 최대 공약수가 되는 것

 

 

# 최대 공약수 (greatest common divisor)

gcd(x,y) = gcd(s,x%y)  if y>0
gcd(x,0) = x

 

 

- 최대 공약수를 구하는 알고리즘

  > y가 0이면 x를 그대로 최대 공약수로 반환하여 종료

  > 그렇지 않으면(y!=0) y와 x%y를 인자로 사용하여 다시 gcd 함수를 호출

  > 재귀 호출이 반복되어 y가 0에 도달하는 순간 재귀 호출이 종료

  > 종료되면 그때 gcd의 반환값(x)이 최대 공약수가 됨

- 예시1: 48과 8의 최대 공약수

  > gcd(48,8) = gcd(8,48%8) = gcd(8,0) = 8

- 예시2: 128과 12의 최대 공약수

  > gcd(128,12) = gcd(12,128%12) = gcd(12 ,8) = gcd(8,12%8) = gcd(8,4)

     = gcd(4,8%4) = gcd(4,0) = 4

 

[코드]

#include <stdio.h>

int gcd(int x, int y);

int main() {
    int x=128, y=12;
    printf("gcd( %d, %d ) = %d \n",x,y,gcd(x,y));
}

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

 

 

 

[실행결과]