Here is another simple program of greatest common divisor (GCD) implementation -

**Euclid's Algorithm**:

while m is greater than zero:

If n is greater than m, swap m and n.

Subtract n from m.

n is the GCD

**Simple python code :)**

import sys

line = sys.stdin.readline()

[n,m] = line.split(None)

n = int(n)

m = int(m)

def gcd(n,m):

while(m > 0):

if(n > m):

t = m

m = n

n = t

m = m - n

print n

gcd(n,m)

**Sample Input/Output**$ python gcd.py

6 15

3

$ python gcd.py

17 8

1

$ python gcd.py

27 9

9

## No comments:

## Post a Comment