Trusted answers to developer questions

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.

The **GCD** of two integers (a, b), denoted by `gcd(a,b)`

, is defined as the largest positive integer * d* such that

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
be any common divisor of**d**and**a**, which implies**b**and**d|a**implies that**d|b**which in turn implies that**d|(a – bq)**.**d|r** - Let
be any common divisor of b and r, which implies that**e**,**e|b**which in turn implies that**e|r****e|(bq + r)**

- This way, we can get
. Hence, any common divisor of**e|a**and**a**must also be a common divisor of**b**, and any common divisor of**r**and**b**must also be a divisor of**r**, which implies that**a**is a common divisor of**d**and**a**if, and only if,**b**is a common divisor of**d**and**b**.**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() { // your code goes here 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

Related Courses