5.13. Разложение на простые множители, вычисление нод и нок

В библиотеке mathn определены также некоторые новые методы в классе Integer. Так, метод gcd2 служит для нахождения наибольшего общего делителя (НОД) объекта, от имени которого он вызван, и другого числа.

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

Метод prime_division выполняет разложение на простые множители. Результат возвращается в виде массива массивов, в котором каждый вложенный массив содержит простое число и показатель степени, с которым оно входит в произведение.

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

                             # To есть 2**1 * 3**2 * 7**1

Имеется также метод класса Integer.from_prime_division, который восстанавливает исходное число из его сомножителей. Это именно метод класса, потому что выступает в роли «конструктора» целого числа.

factors = [[2,1],[3,1],[7,1]]

num = Integer.from_prime_division(factors) # 42

Ниже показано, как разложение на простые множители можно использовать для отыскания наименьшего общего кратного (НОК) двух чисел:

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.1cm(150) # 150

p 2.1cm(3)    # 6

p 4.1cm(12)   # 12

p 200.1cm(30) # 600