The GCD or greatest common divisor of two or more positive numbers is the greatest number which divides each number completely (Leaving no remainder). For example 6 and 18 are divisible by 2, 3, and 6. But 6 is the greatest number among 2, 3 and 6. Thus 6 is the GCD of 6 and 18. Similarly GCD of 10, 15 and 35 is 5. GCD is also known as HCF or Highest Common Factor.

## ALGORITHM TO FIND GCD OF TWO NUMBERS

**(GCD of Two Numbers)** Let A and B are two positive integers. This algorithm finds the GCD of A and B. In this algorithm first A and B will be compared. If A is equal to B then GCD is also equal to A or B. If A is greater than B then A = A – B and repeat the above process. If A is less than B then interchange the values of A and B, and the repeat the same process when A is greater than B. This process will be going on till A is not equal to B. After completion of these steps the GCD will be equal to changed value A.

Step 1: Start

Step 2: [ Take Inputs ] Read: A and B

Step 3: Repeat While A ≠ B

Step 3a: Check If A > B Then

A = A – B

Else

[ Swapping is Done here] Set: Temp = A, A = B and B = Temp

Goto Step 3a.

[ End of If Else Structure ]

[ End of While Loop ]

Step 4: Print: GCD of the two Numbers is A.

Step 5: Exit

### FLOWCHART TO FIND GCD OF TWO NUMBERS

## EUCLID’S ALGORITHM TO FIND GCD OF TWO NUMBERS

Euclid’s algorithm was given by an ancient Greek mathematician Euclid. This algorithm is used to find the GCD of two number by reducing them untill they becomes equal. This algorithm will find the GCD of numbers A and B.

Step 1: Start

Step 2: [ Take Inputs ] Read: A and B

Step 3: Compute: X = A – (A/B)*B

Step 4: Repeat While X ≠ 0

Set: A = B

Set: B = X

Compute: X = A – (A/B)*B

[ End of While Loop ]

Step 5: Print: GCD of the two Numbers is B.

Step 6: Exit

### FLOWCHART TO FIND GCD OF TWO NUMBERS BY EUCLID’S ALGORITHM

## ALGORITHM TO FIND GCD OF THREE NUMBERS

**(GCD of Three Numbers)** Let A, B and C are three positive Integers. This algorithm will find GCD of A, B and C. The GCD of A, B and C will be found in two sections. In the first section GCD of A and B will be found. And in the second section GCD of C and the value obtained from GCD of A and B will be found. And at the end we will get the GCD of A, B and C.

Step 1: Start

Step 2: [ Take Inputs ] Read: A, B and C

Step 3: Compute: X = A – (A/B)*B

Step 4: Repeat While X ≠ 0

Set: A = B

Set: B = X

Compute: X = A – (A/B)*B

[ End of While Loop ]

[ GCD of A and B is stored in B ]

Step 5: Compute: X = B – (B/C)*C

Step 6: Repeat While X ≠ 0

Set: B = C

Set: C = X

Compute: X = B – (B/C)*C

[ End of While Loop ]

[ GCD of B and C is stored in C ]

Step 7: Print: GCD of the Three Numbers is C.

Step 8: Exit