Greatest Common Divisor

Task: write a function called GCD that prints the greatest common divisor of two positive integers (a and b). Hint: you can use the fact that GCD(a, b) = GCD(b, a mod b) and GCD(a, 0) = a

This is my “proper” solution. Written in portable shell script (not bash, but also works in bash), returns only the denominator so that it can be used further as a function, even if it’s not actually one. Easily converted. Assumes good faith, doesn’t check if the input is indeed a number.

#!/bin/sh

A=$1
B=$2
MOD=0

if test $A -eq 0 -o $B -eq 0; then
    printf "none of the numbers can be 0\n"
    return 1
fi

# make sure that A is the bigger number
if test $A -lt $B; then
    A=$2
    B=$1
fi

# gcd($A, $A % $B) until we run out of $B
while test $B -ne 0; do
    MOD=`expr $A % $B`
    A="$B"
    B="$MOD"
    if test $A -eq $B; then
        $A=1
        $B=0
    fi
done

printf "$A"

Took me a while, figuring out the algorithm, finding out (again) how to do math in shell and finding some gotchas. However, here’s another one, the modern sysadmin’s solution, in Python, this one is much faster to write:

# I don't speak Pythonian
a=int(raw_input("first number:  "))
b=int(raw_input("second number: "))
div_a=[]
div_b=[]

if a <= 0 or b <= 0:
    print "only positive numbers > 0 please"
    quit()

for i in range(1, a + 1):
    if a % i == 0:
        div_a.append(i)

for i in range(1, b + 1):
    if b % i == 0:
        div_b.append(i)

for i in div_a:
    if i in div_b:
        gcd = i

print gcd