# Caribbean Secondary Education Certificate - Information Technology/Converting Algorithms to Programs

## Example

Problem: Find the greatest common divisor (GCD) of two integers, m and n.

Euclid's Algorithm:

while m is greater than zero:

  If n is greater than m, swap m and n.
Subtract n from m.


n is the GCD

Program (in C): int gcd(int m, int n) /* precondition: m>0 and n>0. Let g=gcd(m,n). */

{ while( m > 0 )
{ /* invariant: gcd(m,n)=g */
if( n > m )
{ int t = m; m = n; n = t; } /* swap */
/* m >= n > 0 */
m -= n;
}
return n;
}