给定数字的所有因数

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

[[1,4800]，[2,2400]，[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]]

您如何在ruby或任何语言中实现此功能？

- thenengah

---

术语错误。您要寻找的是“因素”（factors） 。 - Michael Borgwardt

@Michael Borgwardt: 不，他特别是在寻找“因数”。虽然找到“因子”（首先），再从中生成“因数”（第二）可能是解决这个问题的最佳方法。 - AnT stands with Russia

@Beta, @AndreyT, @Vatine：我从未听说过“factors”代表“质因数”的惯例，它通常是与“约数”同义的。你们能提供这种惯例的引用吗？（如果确实存在这样的惯例，那么为什么我们还需要使用形容词“质数”呢？） - ShreevatsaR

这是美式英语（factors 意味着质因数）和英式英语（factors 意味着因子）之间的区别。 - user448810

作为背景信息，我是一个在美国大学学习数学的美国人。根据我的经验，如果有人想表达“质因数”，我会期待他们说“prime factors”。无论是英式还是美式英语，因子未必都是质数。 - Greg

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...

- Marc-André Lafortune

---

太好了。这种解决方案，例如对于number=12，执行(2^0, 2^1, 2^2) x (3^0, 3^1) — 对于大型（尤其是复合）数字比问题中的代码快得多。Ruby看起来很酷！ - ShreevatsaR

有人能用数学的方式解释一下“factors_of”吗？ - oppih

质因数分解显示了一组质数的组合，当它们相乘时等于该数字。然而，除以其中任何一个质数都会产生一个具有类似质因数分解但被除数不同的数字。例如，pf(4800) = 2^635^2。除以2，你就得到pf(2400) = 2^535^2，再除以2，pf(1200) = 2^435^2。这个过程迭代了所有可能的组合。 - Eric Haynes

Answer 2

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

- bluexuemei

---

以及 1...num 作为合适的除数 - Ulysse BN

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

- lipanski

---

你的代码有一个错误。 irb(main):026:0> 64.paired_up_factors => [[1, 64], [2, 32], [4, 16], 8, 8] 最后一组应该是[8,8]。 - EnabrenTane

把最后一个加数([a[l / 2], a[l / 2]])用另一个[括号包起来有帮助吗？ - Katrin Leinweber

Answer 4

使用暴力破解算法，你可以跳过一半的数字，因为对于n来说，大于n / 2的数字显然不能是约数，所以为了加速计算，你可以从n到n / 2，然后只需添加n本身。我还为n = 1的情况添加了.uniq：

((1..(n / 2.0).ceil).select { |i| n % i == 0 } + [n]).uniq

- Rustam Gasanov

---

实际上，这个上限是 Math.sqrt(n)，而不是 n / 2.0。 - nzifnab

一个简单的证明：令 x = Math.sqrt(num).to_i。我们希望证明对于每个满足 n > x 的 num 的因子 n，相应的因子 num/n 都小于 x。这是因为 num/n = x*num/x*n < x*num/x*x = x*num/x*x = x*num/num = x。我们可以计算每个因子 f 直到 num**0.5 并添加相应的因子 num/f。 - Cary Swoveland

Answer 5

这是Ruby代码。

require 'prime'

def divisors(n)
  arr = Prime.prime_division(n).map { |v,exp| (0..exp).map { |i| v**i } }
  arr.first.product(*arr[1..-1]).map { |a| a.reduce(:*) }.map { |m| [m,n/m] }
end

例如，

divisors 24
  #=> [[1, 24], [3, 8], [2, 12], [6, 4], [4, 6], [12, 2], [8, 3], [24, 1]] 
divisors 9
  #=> [[1, 9], [3, 3], [9, 1]] 
divisors 450
  #=> [[1, 450], [5, 90], [25, 18], [3, 150], [15, 30], [75, 6], [9, 50],
  #    [45, 10], [225, 2], [2, 225], [10, 45], [50, 9], [6, 75], [30, 15],
  #    [150, 3], [18, 25], [90, 5], [450, 1]] 

对于n = 24，步骤如下：

a   = Prime.prime_division(n)
  #=> [[2, 3], [3, 1]] 
arr = a.map { |v,exp| (0..exp).map { |i| v**i } }
  #=> [[1, 2, 4, 8], [1, 3]] 
b   = arr.shift
  #=> [1, 2, 4, 8] 
arr
  #=> [[1, 3]] 
c   = b.product(*arr)
  #=> [[1, 1], [1, 3], [2, 1], [2, 3], [4, 1], [4, 3], [8, 1], [8, 3]] 
d   = c.map { |a| a.reduce(:*) }
  #=> [1, 3, 2, 6, 4, 12, 8, 24] 

最后，

d.map { |m| [m,n/m] }

返回上述给定的数组。

- Cary Swoveland

Answer 6

Python自带的功能无法进行因数分解，但是可以使用以下方法开始实现：

>>> p=[[2, 6], [3, 1], [5, 2]]

>>> from itertools import product
>>> print sorted(reduce(lambda x,y:x*y,j) for j in product(*[[x**i for i in range(0,y+1)] for x,y in p]))
[1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 20, 24, 25, 30, 32, 40, 48, 50, 60, 64, 75, 80, 96, 100, 120, 150, 160, 192, 200, 240, 300, 320, 400, 480, 600, 800, 960, 1200, 1600, 2400, 4800]

- John La Rooy

---

这个问题是关于 Ruby 的。不是 Python。 - Mohamad

@Mohamad，那么“或任何语言”对你来说意味着什么？ - John La Rooy

可以，但问题应该标记为语言无关，而不是 Ruby。 - Mohamad

Answer 7

您还可以使用 O(sqrt(n)) 的算法，而无需素因数分解。如果您查看列表中的每对 [a，b]，使得 a <= b，则也会出现一对 [b，a]。这使您只需迭代至 sqrt(n) 即可，因为 a <= sqrt(n)。

要证明对于每一对 [a，b]，满足 a <= b 都成立 a <= sqrt(n)，可以使用反证法来证明。假设 a > sqrt(n)。如果 a > sqrt(n)，那么 b > sqrt(n)，因为 b >= a。因此： a * b > sqrt(n) * sqrt(n) = n 这与 a * b == n 的事实相矛盾。因此以下算法将生成所有对（以下代码为 C++）：

void GeneratePairs(int n) {
  for (int a = 1; a <= n / a; ++a)
    if (n % a == 0) {
      const int b = n / a;
      printf("[%d, %d] ", a, b);
      if (a != b)  // be careful with square numbers
        printf("[%d, %d] ", b, a);
    }
  printf("\n");
}

唯一的问题是这段代码不能按顺序生成对。一种解决方法是将它们存储在一个向量中，进行排序，然后打印它们，或者进行两次遍历，一次正向遍历，一次反向遍历：

void GeneratePairsTwoPasses(int n) {
  const int sq = static_cast<int>(sqrt(n));
  for (int a = 1; a <= sq; ++a)
    if (n % a == 0)
      printf("[%d, %d] ", a, n / a);
  for (int a = sq - 1; a >= 1; --a)
    if (n % a == 0)
      printf("[%d, %d] ", n / a, a);
  printf("\n");
}

- jbernadas

Answer 8

这个问题实际上并不询问除法的结果，您可以通过将数组转换为参数数组来调用乘积。

n= 4800
pd= n.prime_division.map{ |pd| (0..pd[1]).map{ |i| pd[0]** i } }
p (pd.length== 1 ? pd[0] : pd[0].product(*pd.drop(1)).map{ |a, b| a* b })[0..-2].uniq

- nurettin

---

我还顺便把n从约数列表中删除了。 - nurettin

如果您没有删除 1 和 n，那么您的答案会更清晰。毕竟，只有返回的数组包含两个元素时，该数字才是质数。另外，您需要使用 uniq 吗？ - Cary Swoveland

Answer 9

在 Haskell 中，任何一个都可以：

import Control.Monad

factorsOf :: (Integral a) => a -> [(a,a)]
factorsOf n = [(x,n `div` x) | x <- [1..n], n `mod` x == 0]

factorsOf_ :: (Integral a) => a -> [(a,a)]
factorsOf_ n = do
    x <- [1..n]
    guard (n `mod` x == 0)
    return (x, n `div` x)

- keiter

---

这个方法通过从1到n的每个整数进行试除，对于大的n来说效率极低。 - ShreevatsaR

是的，如果性能是一个问题，你绝对不应该使用这段代码。 :) - keiter

OP正在寻求Ruby方面的帮助。Haskell如何对他有所帮助？ - Mohamad

Answer 10

在 F# 中：

let factors n = [for i in 1..n do if n%i=0 then yield i]

其他语言的实现可以在 Rosetta Code这里找到。

- Ben Griswold

---

问题是“你会如何在Ruby或任何语言中实现这个？” - Ben Griswold