|
The Euclidean Algorithm One way to find the greatest common denominator of two positive integers is to use the Euclidean Algorithm. This is how it works: Pick two numbers, say (377,18). You divide the larger by the smaller of the two and find out what your remainder is. In this case, 377 can be divided by 18 20 times with a remainder of 17. The next step is to replace the larger number with the smaller and replace the smaller with the remainder. So, the next pair becomes (18,17). We keep on repeating (looping) through this process until we have zero. We divide 18 by 17 and the next pair becomes (17,1). Another time through and we arrive at (1,0). So, the answer is 1. The whole progression looks like this: (377,18) (18,17) (17,1) (1,0) Copy and paste this program into your compiler. Save it as "Euclid." program Pay particular attention to how the program sorts out the users numbers to put them in order. |