Euclid’s algorithm

Side Note: This is first written on Oct 17 2007.

Euclid’s algorithm is used to find the greatest common divisor for two positive integers, let’s say m and n. It’s the first algorithm introduced in Knuth’s classic book, <<The Art of Computer Programming >> . The following text are retrieved from the book,

a. [Find remainder] Divide m by n and let r be the remainder.
(0<=r and r< n).
b. [Is it zero] If r = 0, terminates the program; n is the answer.
c. [Reduce] Set m = n, n = r, and go back to step a. 

A C/C++ implementation of the above algorithm is as follows,

//please ensure that variables passed to the function is positive 
int euclid(int m, int n) {
	int r = m%n;
	while(r!=0) {
	    m = n;
	    n = r;
	    r = m%n;
        }
	return n;
}

This algorithm/program can also be used to decide whether two positive integers are relative prime(no common divisor except one) or not. All we need to do is to check the return value is 1 or not.