Related Tags

gcd
interview
communitycreator
number theory
c++

# How to find the greatest common divisor

Harsh Jain

In this article, we will discuss a very popular algorithm that is generally used in interview coding questions. The aim is to find the greatest common divisor (GCD) between two numbers. The optimized algorithm is pretty fast as compared to the brute force approach.

## Greatest common divisor (GCD) using Euclid’s algorithm

The GCD of two integers (a, b), denoted by gcd(a,b), is defined as the largest positive integer d such that d | a and d | b where x | y implies that x divides y.

Example of GCD:

• gcd(4, 8) = 4
• gcd(10, 5) = 5
• gcd(20,12) = 4

According to the Euclid’s Algorithm:

gcd(A,B) = gcd(B,A%B) // recurrence for GCD

gcd(A,0) = A // base case


Let’s discuss the proof of the recurrence.

Proof:

• If a = bq + r.
• Let d be any common divisor of a and b, which implies d|a and d|b implies that d|(a – bq) which in turn implies that d|r.
• Let e be any common divisor of b and r, which implies that e|b , e|r which in turn implies that e|(bq + r)
• This way, we can get e|a. Hence, any common divisor of a and b must also be a common divisor of r, and any common divisor of b and r must also be a divisor of a, which implies that d is a common divisor of a and b if, and only if, d is a common divisor of b and r.

The GCD of more than 2 numbers, e.g., gcd(a,b,c) is equal to gcd(a,gcd(b,c)) and so on.

int gcd(int a, int b) {
return (b == 0 ? a : gcd(b, a % b));
}

int main() {
int a = 100, b = 20;
int result;
result = gcd(a,b);
cout << result;
}
GCD using Euclid's Algorithm

Explanation:

• The above function, gcd(), accepts two numbers as input and provides the output. As we are using the % operator, the number of recursive calls required to reach the final result would be less than n where n = max(a,b).
• Euclid’s GCD algorithm runs in $O(log(N))$, where $N$ = $max(a,b)$.

RELATED TAGS

gcd
interview
communitycreator
number theory
c++

CONTRIBUTOR

Harsh Jain
RELATED COURSES

View all Courses

Keep Exploring

Learn in-demand tech skills in half the time