Home » ALGORITHM » ALGORITHM TO FIND GREATEST COMMON DIVISOR

# ALGORITHM TO FIND GREATEST COMMON DIVISOR

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

## 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

## 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

### Related Posts

• ALGORITHM AND FLOWCHART FOR COPRIME NUMBER A Coprime number comes in pair of integers. Thus they are defined as those paired numbers which can be divided by the common number 1 are called coprime numbers. Suppose a and b are two […] Posted in ALGORITHM
• ALGORITHM AND FLOWCHART FOR COMPOSITE NUMBER Those numbers which are divisible by other than itself and 1 are known as composite numbers. The number 4 can is divisible by 1, 2 and 4 therefore 4 is a composite number. But 7 is […] Posted in ALGORITHM
• ALGORITHM TO CHECK EVEN AND ODD NUMBERS A number is said to be even number if it leaves no remainder when divided by 2. There is an alternative definition of even number and it is as a number having any number from 0, 2, 4, 6 […] Posted in ALGORITHM
• SORTING ALGORITHM There are different sorting algorithm like Selection Sort, Bubble Sort, Insertion Sort, Merge Sort and Heap Sort. This topic only covers two of them these are Selection Sort Algorithm and […] Posted in ALGORITHM