Euclids Algorithm
Ruby
code posted
by
chaitanya
created at 02 Aug 07:13
Edit

Back
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 
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 
740 Bytes in 9 ms with coderay