GCD (Greatest Common Divisor) of Two Numbers

GCD (Greatest Common Divisor) of Two Numbers-

The greatest number which is a common factor of two or more given numbers is called GCD (Greatest Common Divisor).

Suppose two numbers are given. Now, divide the greater number by the smaller one. Next, divide the divisor by the remainder. Continue on repeating the process of dividing the preceding divisor by the remainder last obtained, till the remainder zero is obtained. Then the last divisor is the required GCD of given number. Suppose you want to find GCD of 112 and 152, then 

say, x = 112 i.e. Smaller number, so will be divisor

       y = 152 i.e. Greater number, so will be dividend

Step-

Therefore, the greatest common divisor is 8

Algorithm-

1. Begin
2. Get 1st and 2nd integer number, i.e. x and y
3. Check which number is larger.
4. Get the remainder by dividing the greater number by the smaller number.
5. Now make smaller number dividend and divide the dividend by the divisor get the remainder. Let remainder be the divisor.
6. Repeat step 4, 5, and 6 until a zero remainder is obtained. Now, the last divisor is the GCD.
7. Stop