All divisors of a given number

Question

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

 # num = the number you want factors of

 def divisors_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?

Answer 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' or modify the inject above...

Answer 2

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)

Answer 3

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]

Answer 4

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.

Answer 5

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