Integer#gcd と Integer#gcd2 - y_tsuda's blog - s21g

Rubyには、最大公約数を求めるInteger#gcd と Integer#gcd2がある。 「gcd"2"ってなんやねん！」と気になったので、実装を見てみた。 1 # File lib/mathn.rb, line 19 2 def gcd2(int) 3 a = self.abs 4 b = int.abs 5 a, b = b, a if a < b 6 7 pd_a = a.prime_division 8 pd_b = b.prime_division 9 10 gcd = 1 11 for pair in pd_a 12 as = pd_b.assoc(pair[0]) 13 if as 14 gcd *= as[0] ** [as[1], pair[1]].min 15 end 16 end 17 return gcd 18 end