Книга: Программирование на языке Ruby

5.13. Разложение на простые множители, вычисление НОД и НОК

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

Оглавление книги