58 Chapter 5 Program Looping
There is a procedure or algorithmthat can be followed to arrive at the gcdof two arbi-
trary integers.This algorithm is based on a procedure originally developed by Euclid
around 300 B.C., and can be stated as follows:
Problem: Find the greatest common divisor of two nonnegative integers u
and v.
Step 1: If vequals 0 , then you are done and the gcdis equal to u.
Step 2: Calculate temp = u % v,u = v,v = temp, and go back to step 1.
Don’t concern yourself with the details of how the preceding algorithm works—simply
take it on faith. Focus more here on developing the program to find the greatest com-
mon divisor than on performing an analysis of how the algorithm works.
After the solution to the problem of finding the greatest common divisor has been
expressed in terms of an algorithm, it becomes a much simpler task to develop the com-
puter program. An analysis of the steps of the algorithm reveals that step 2 is repetitively
executed as long as the value of vis not equal to 0 .This realization leads to the natural
implementation of this algorithm in C with the use of a whilestatement.
Program 5.7 finds the gcdof two nonnegative integer values typed in by the user.Program 5.7 Finding the Greatest Common Divisor
/* Program to find the greatest common divisor
of two nonnegative integer values */#include <stdio.h>int main (void)
{
int u, v, temp;printf ("Please type in two nonnegative integers.\n");
scanf ("%i%i", &u, &v);while ( v != 0 ) {
temp = u % v;
u = v;
v = temp;
}printf ("Their greatest common divisor is %i\n", u);return 0;
}