Monday, March 12, 2012

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

No comments:

Post a Comment