Math For DSA

GCD (Greatest common divisor) :

The greatest common divisor (GCD) of two or more numbers is the greatest common factor number that divides them, exactly. It is also called the highest common factor (HCF). For example, the greatest common factor of 15 and 10 is 5, since both numbers can be divided by 5.

15/5 = 3

10/5 = 2

If a and b are two numbers then the greatest common divisor of both the numbers is denoted by gcd(a, b). To the gcd of numbers, we need to list all the factors of the numbers and find the largest common factor.

Suppose, 4, 8, 16 are three numbers. Then the factor of 4, 8 and 16 are :

4 → 1,2,4

8 → 1,2,4,8

16 →  1,2,4,8,16

Therefore, we can conclude that 4 is the highest common factor among all three numbers.


How to find the GCD

Before we move ahead on finding GCD of a numbers, let understand what  a factor and common factors are ?

What are Factors ?

Factors of a number divides the original number evenly. For example, if 8 is the factor of 64, then 8 can divide 64 into 8 equal parts.

What are Common Factors ?

If factor of a number is a factor of another number, then it is said to be a common factor for the two numbers. For example, 2 is a factor of 4 and 8, hence 2 is a common factor.

Methods to find GCD 

There are several methods to find the GCD of given two numbers.

1. Prime factorisation method

2. Long division method

3. Euclid's division algorithm


Euclid's Algorithms Formula : 

gcd(a, b) = 

gcd(a-b, b)   [ a > b ]  

            and 

gcd(a, b-a )    [ b > a]


GCD code in c++ given below --