All factors of a given number

问题:

For example, I have 4800 and I would like to see all the factors of this number.

 # 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]]

How would you do this in ruby or any language?

回答1:

In Ruby, the prime library gives you the factorization:

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

To get that list of yours, you take the cartesian product of the possible powers:

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

Note: In Ruby 1.8.7, you must require 'mathn' instead of require 'prime'. In Ruby 1.8.6, require 'backports/1.8.7/enumerable/inject' or modify the inject above...

回答2:

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

回答3:

I think this solution is nicer, especially because it doesn't perform so many loops, it doesn't require the Prime library and most importantly it runs til Math.sqrt(n). Here's the code:

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

If you want to pair them up, just like in your example, you can use the following piece of code (which pairs up first with last and in case there's an odd number of factors, then the middle one is the square root):

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

回答4:

You could also do an O(sqrt(n)) algorithm that does not need prime factorization. If you see at your list, for every pair [a, b] in your list such that a <= b, the pair [b, a] also appears. This allows you to iterate only up to sqrt(n), because a <= sqrt(n).

To prove that for every pair [a, b] such that a <= b it holds that a <= sqrt(n) you can use a proof by contradiction. Let's assume that a > sqrt(n). If a > sqrt(n), then b > sqrt(n) too, because b >= a. Therefore:

a * b > sqrt(n) * sqrt(n) = n

which contradicts the fact that a * b == n. So the following the algorithm will generate all pairs (the following code is in 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");
}

The only issue is that this code does not generate the pairs in order. One solution is to store them in a vector, sort them and then print them, or doing two passes, one forward and one backwards:

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");
}

回答5:

Python doesn't come with batteries to do the factorisation, but starting with

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

回答6:

The question doesn't really ask about the results of the divisions, and you can call product by converting array of arrays to array parameters.

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

回答7:

Using brute force, you can skip half of the numbers, since for n, numbers greater than n / 2 obviously can't be divisors, so to speed up calculation, you can go from n to n / 2 and then just add n itself. I've also added .uniq for n = 1 case:

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

回答8:

In Haskell, any of these two:

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)

回答9:

In F#:

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

Other language implementations can be found here at Rosetta Code.

回答10:

This is Ruby code.

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

For example,

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

For n = 24, the steps are as follows:

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] 

Lastly,

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

returns the array given above.

回答11:

def divisors(n)
  divisors = []    # Initialize an empty array where we store our divisors
  for i in 1..n
    divisors.push([i,n-i]) if n % i == 0    # Only pushes if i is a divisor of n
  end
  divisors      # returns our array
end