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).

Procedure for finding the GCD:

Suppose we take two numbers as x=190 and y=300. Divide the greater number by the smaller one. Next, divide the divisor by the remainder. Repeat the process until the remainder becomes zero. So the last divisor is the required GCD (Greatest Common Divisor).

Here greater number is y=300 and smaller number is x=190.

Dividend              Operator             Divisor  Remainder

300                         /                              190                         110

110                         /                              190                         0

Therefore, the GCD is 110.

Algorithm:

Step 1: Start

Step 2: Take first and second number.The number should be non-zero integers, i.e.a,b.

Step 3: Check which integer is larger.

Step 4: Get the remainder by dividing the greater integer by the smaller integer.

Step 5: Let smaller integer be dividend.

Step 6: Let remainder be the divisor.

Step 7: Repeat step 4, step 5, and step 6 until the remainder becomes zero. Now the last divisor is the GCD (Greatest Common Divisor)

Step 8: Stop.