给定数量的所有因素

Question

例如,我有4800,我想看到这个数字的所有因素.

 # num = the number you want factors of

 def factors_of(num)
    (1..num).collect { |n| [n, num/n] if ((num/n) * n) == num}.compact
 end

divisors_of(4800)=> [[1,4800],[2,2,400],[3,1600],[4,1200],[5,960],[6,800],[8,600],[ 10,480],[12,400],[15,320],[16,300],[20,240],[24,200],[25,192],[30,160],[32, 150],[40,120],[48,100],[50,96],[60,80],[64,75],[75,64],[80,60],[96,50] ,[100,48],[120,40],[150,32],[160,30],[192,25],[200,24],[240,20],[300,16],[ 320,15],[400,12],[480,10],[600,8],[800,6],[960,5],[1200,4],[1600,3],[2400, 2],[4800,1]]

你会用红宝石或任何语言做到这一点？

Answer 1

在Ruby中,prime库为您提供分解:

require 'prime'
4800.prime_division #=> [[2, 6], [3, 1], [5, 2]]

要获得你的名单,你可以获得可能的权力的笛卡尔积:

require 'prime'
def factors_of(number)
  primes, powers = number.prime_division.transpose
  exponents = powers.map{|i| (0..i).to_a}
  divisors = exponents.shift.product(*exponents).map do |powers|
    primes.zip(powers).map{|prime, power| prime ** power}.inject(:*)
  end
  divisors.sort.map{|div| [div, number / div]}
end

p factors_of(4800) # => [[1, 4800], [2, 2400], ..., [4800, 1]]

注意:在Ruby 1.8.7中,您必须require 'mathn'代替require 'prime'.在Ruby 1.8.6中,require 'backports/1.8.7/enumerable/inject'或者修改inject上面的...

Answer 2

 def divisors_of(num)
   (1..num).select { |n|num % n == 0}
 end

Answer 3

我认为这个解决方案更好,特别是因为它不执行如此多的循环,它不需要Prime库,最重要的是它运行直到Math.sqrt(n).这是代码:

class Integer
  def factors
    1.upto(Math.sqrt(self)).select {|i| (self % i).zero?}.inject([]) do |f, i| 
      f << i
      f << self / i unless i == self / i
      f
  end.sort
end

# Usage
4800.factors

如果你想将它们配对,就像在你的例子中一样,你可以使用下面的一段代码(首先与最后一对配对,如果有奇数个因子,那么中间的一个是平方根):

class Integer
  def paired_up_factors
    a = self.factors
    l = a.length
    if l % 2 == 0
      a[0, l / 2].zip(a[- l / 2, l / 2].reverse)
    else
      a[0, l / 2].zip(a[- l / 2 + 1, l / 2].reverse) + [a[l / 2], a[l / 2]]
    end
  end
end

# Usage
4800.paired_up_factors