Euclids Algorithm

class Gcd
  #GCD(m,n)
  # Step 1 : Divide m/n and r is the remainder 0<=r<=n
  # Step 2   if r = 0 then n is the GCD of m,n
  # r !=0 then m =n and n =r go to step 1
  # m can be less than n to make the algorithm faster make sure m is greater than n
  #
  # e.g   2322, 654
  #       1071, 1029
  #       1769,551
  #       2166,6099
  #       163231, 135749
  attr_accessor :m, :n

  def initialize(m, n)
    m, n = m.to_i, n.to_i
    if (m > n)
      @m, @n = m, n
    else
      @m, @n = n, m
    end
    compute(m, n)
  end

  def compute(m, n)
    r = nil #
    p Time.now
    while (r = m % n)!= 0
      m = n
      n = r
    end
    p "The GCD of #{@m}, #{@n} is #{n}"
    p Time.now
  end
end