# Greatest Common Divisor Calculator in Python

In mathematics, the **greatest common divisor** (**GCD**) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers *x*, *y*, the greatest common divisor of *x* and *y* is denoted gcd(x,y). For example, the GCD of 8 and 12 is 4, that is, gcd(8,12)=4

gcd(12,9) = 3

gcd(10,6) = 2 and so on..In the name "greatest common divisor", the adjective "greatest" may be replaced by "highest", and the word "divisor" may be replaced by "factor", so that other names include **greatest common factor** (**gcf**).

### GCD

Code:

**def** gcd(a,b):
**if** b==0:
**return** a
**else**:
**return**(gcd(b,a%b))

**if** __name__ == "__main__":
two_inputs = input()
a, b = map(int, two_inputs.split())
print(gcd(a, b))

In this code we used the Euclidian algorithm which is as follows:

The Algorithm

The Euclidean Algorithm for finding GCD(A,B) is as follows:

If A = 0 then GCD(A,B)=B, since the GCD(0,B)=B, and we can stop.

If B = 0 then GCD(A,B)=A, since the GCD(A,0)=A, and we can stop.

Write A in quotient remainder form (A = B⋅Q + R)

Find GCD(B,R) using the Euclidean Algorithm since GCD(A,B) = GCD(B,R)

Example:

Find the GCD of 270 and 192

A=270, B=192

A ≠0

B ≠0

Use long division to find that 270/192 = 1 with a remainder of 78. We can write this as: 270 = 192 * 1 +78

Find GCD(192,78), since GCD(270,192)=GCD(192,78)

A=192, B=78

A ≠0

B ≠0

Use long division to find that 192/78 = 2 with a remainder of 36. We can write this as:

192 = 78 * 2 + 36

Find GCD(78,36), since GCD(192,78)=GCD(78,36)

A=78, B=36

A ≠0

B ≠0

Use long division to find that 78/36 = 2 with a remainder of 6. We can write this as:

78 = 36 * 2 + 6

Find GCD(36,6), since GCD(78,36)=GCD(36,6)

A=36, B=6

A ≠0

B ≠0

Use long division to find that 36/6 = 6 with a remainder of 0. We can write this as:

36 = 6 * 6 + 0

Find GCD(6,0), since GCD(36,6)=GCD(6,0)

A=6, B=0

A ≠0

B =0, GCD(6,0)=6

**So we have shown:**

GCD(270,192) = GCD(192,78) = GCD(78,36) = GCD(36,6) = GCD(6,0) = 6

**GCD(270,192) = 6**

Though in the code we have used the same manner, a function called gcd() does the whole job, it takes the two inputs and repeatedly do the calculations, it finds b%a and recall the same function giving inputs as (b, b%a), it repeatedly does this until a is found to be 0, it then can return b; otherwise it will keep working recursively until the Greatest Common Divisor is found and returns it.

Resources for explanation:

Example and explanation provided from Khan Academy explanation it was very helpful made me understand that's why I shared it to help people understand the idea

## Comments