The following snippet is copied from the book(Structure and Interpretation of Computer Programs 1.2.5)
-----------------------------------------------
The greatest common divisor (GCD) of two integers a and b is defined to be the largest integer that divides both a and b with no remainder.
The idea of the algorithm is based on the observation that, if r is the remainder when a is divided by b, then the common divisors of a and b are precisely the same as the common divisors of b and r. Thus, we can use the equation
GCD(a,b) = GCD(b,r)
to successively reduce the problem of computing a GCD to the problem of computing the GCD of smaller and smaller pairs of integers. For example,
GCD(246,40) = GCD(40,6)
= GCD(6，4)
= GCD(4，2)
= GCD(2，0)
= 2
reduces GCD(206,40) to GCD(2,0), which is 2. It is possible to show that starting with any two positive integers and performing repeated reductions will always eventually produce a pair where the second number is 0. Then the GCD is the other number in the pair. This method for computing the GCD is known as Euclid's Algorithm.42
--------------------------------------------------
The following code works in VC2005
#include "stdafx.h"
#include <stdio.h>
/*
function: gcd
input: a,b
output: the gcd of integer a and b
*/
int gcd(int a, int b)
{
if(0 == b)
{
return a;
}
else
{
return gcd(b, a%b);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int r = gcd(206, 40);
printf("r=%d", r);
r = gcd(40, 206);
printf("r=%d", r);
return 0;
}
remark: Euclid's Algorithm: 欧几里得算法