EXAMPLE OF AN ALGORITHM

Before going into the details of problem-solving with algorithms, just to have an idea of what an algorithm is, we consider a well-known algorithm for finding Greatest Common Divisor (G.C.D) of two natural numbers and also mention some related historical facts. First, the algorithm is expressed in English. Then, we express the algorithm in a notation resembling a programming language.

Euclid’s Algorithm for Finding G.C.D. of two Natural Numbers m & n:

E1. {Find Remainder}. Divide m by n and let r be the (new) remainder {e have 0≤r<n}

E2. {Is r zero?} If r = 0, the algorithm terminates and n is the answer. Otherwise,

E3. {Interchange}. Let the new value of m be the current value of n and the new value of n be the current value of r. Go back to Step E1.

The termination of the above method is guaranteed, as m and n must reduce in each iteration and r must become zero in finite number of repetitions of steps E1, E2 and E3.