欧几里德算法求最大公约数

算法

欧几里德算法又称辗转相除法，用于计算两个整数m, n的最大公约数。

其计算原理依赖于下面的定理：

gcd(m, n) = gcd(n, m mod n)

这个定理的意思是：整数m、n的最大公约数等于n和m除以n的余数的最大公约数。

# author: jtusta
# contact: root@jtahstu.com
# site: http://www.jtahstu.com
# software: RubyMine
# time: 2017/6/7 14:44
class Gcd
  # 循环写法，即非递归写法
  def gcd(m, n)
      while n>0
        m, n = n, m % n
      end
      return m
  end
  # 递归写法
  def gcd_2(m,n)
    return n==0?m:self.gcd_2(n,m%n)
  end
end
c = Gcd.new
res = c.gcd(8,12)
puts res
rec = c.gcd_2(32,24)
p rec