给定数量的所有因素
例如，我有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,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或任何语言做到这一点？
在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 'mathn' require 'prime' 。 在Ruby 1.8.6中， require 'backports/1.8.7/enumerable/inject'或修改上面的inject …
def divisors_of(num) (1..num).select { |n|num % n == 0} end
我认为这个解决方案更好，特别是因为它不执行如此多的循环，它不需要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
您还可以执行不需要素数因子分解的O（sqrt（n））算法。 如果您在列表中看到，对于列表中的每一对[a，b]， a <= b ，那么对[b，a]也会出现。 这允许您仅迭代到sqrt(n) ，因为a <= sqrt(n) 。
为了certificate对于每一对[a，b]使得a <= b它认为a <= sqrt(n)你可以使用矛盾的certificate。 我们假设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(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"); }
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]
问题并不是真正询问分区的结果，您可以通过将数组数组转换为数组参数来调用product。
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
使用蛮力，你可以跳过一半的数字，因为对于n ，大于n / 2数字显然不能成为除数，所以为了加快计算，你可以从n到n / 2然后只添加n本身。 我还为n = 1情况添加了.uniq ：
((1..(n / 2.0).ceil).select { |i| n % i == 0 } + [n]).uniq
在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)
在F＃中：
let factors n = [for i in 1..n do if n%i=0 then yield i]
其他语言实现可以在Rosetta Code中找到。
这是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] }
返回上面给出的数组。
def divisors(n) divisors = [] # Initialize an empty array where we store our divisors for i in 1..n divisors.push([i,ni]) if n % i == 0 # Only pushes if i is a divisor of n end divisors # returns our array end