GCD
by Isai Damier, Android Engineer @ Google

#=======================================================================
# Author: Isai Damier
# Title: Greatest Common Divisor
# Project: geekviewpoint
# Package: algorithms
#
# Statement:
#  Find the greatest common divisor of the given numbers
#
# Sample Input: 18, 27
# Sample Output: 9
#
# Description: This function finds the greatest common
#   divisor of the given numbers. The GCD of x and y is the greatest
#   integer that divides both x and y evenly. For example the gcd of
#   18 and 27 is 9 because 9*3 = 27 and 9*2= 18.
#
# Technical Details: Mathematicians have found numerous techniques
#    for calculating the GCD of two numbers. The present
#    implementation uses the mod operator. Other implementations
#    may use subtraction, for example.
#======================================================================= 
 def GCD( a, b ):
  if 0 == a or 0 == b:
    return -1

  if 1 == a or 1 == b:
    return 1

  while 0 < a and 0 < b:
    if a > b:
      a %= b
    else:
      b %= a

  return 0 == a and b or a

import unittest
from algorithms import numbers as algorithm

class Test( unittest.TestCase ):

  def testAllPrimes( self ):

      expected = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
      self.assertEquals( expected, algorithm.allPrimes( 30 ) )

      expected = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
      self.assertEquals( expected, algorithm.allPrimes( 31 ) )

      expected = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
      self.assertEquals( expected, algorithm.allPrimes( 40 ) )