Section 5.14. Working with Prime Numbers

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)   # 42

The following code is an example of using prime factorization to find the Least Common Multiple (LCM) of a pair of numbers:

require 'mathn' class Integer   def lcm(other)     pf1 = self.prime_division.flatten     pf2 = other.prime_division.flatten     h1 = Hash[*pf1]     h2 = Hash[*pf2]     hash = h2.merge(h1) {|key,old,new| [old,new].max }     Integer.from_prime_division(hash.to_a)   end end p 15.lcm(150)     # 150 p 2.lcm(3)        # 6 p 4.lcm(12)       # 12 p 200.lcm(30)     # 600