유클리드 호제법으로 gcd를 구하는 방법은 다음과 같다:두 자연수 a>b에 대하여 gcd(a,b)=gcd(b,a%b)임을 이용해 두 수 중 큰 것을 작은 것으로 나눠 그 나머지로 대체한다. 이 때 두 수 중 하나가 0이 되면 남은수가 gcd이다. 코드로 구현하면 다음과 같다:int gcd(int a,int b){//a>0, b>0if(b==0)return a;return gcd(b,a%b);}b>a%b이므로 다시 호출되었을 때는 a>b를 만족한다. 그러므로 b가 0인지만 확인하면 된다.a>b를 만족하지 않고 a>0, b>0이기만 해도 된다. 왜냐하면 a이면 gcd(b,a)가 다시 호출되기 때문이다. c언어에서는 a가 음수일 떄 a%b를 음수 또는 0으로 계산하므로 a>0, b>0이도록 해야한다. 양수로 ..