The Ruby Way: Solutions and Techniques in Ruby Programming, Second Edition

5.13. Finding Prime Factorization, GCD, and LCM

The mathn library also defines some new methods on the Integer class. One is gcd2, which finds the greatest common divisor of the receiver and the other specified number:

n = 36.gcd2(120)    # 12
k = 237.gcd2(79)    # 79

The prime_division method performs a prime factorization of its receiver. The result returned is an array of arrays where each smaller array consists of a prime number and its exponent:

factors = 126.prime_division  # [[2,1], [3,2], [7,1]]
                              # i.e. 2**1 * 3**2 * 7**1

There is also a class method Integer.from_prime_division, which reverses that factorization. It is a class method because it is like a “constructor” for an integer.

factors = [[2,1],[3,1],[7,1]] num = Integer.from_prime_division(factors) ...