GCD

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