All factors of a given number

Question

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?

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/1.8.7/enumerable/inject' or modify the inject above...

Answer 2

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

Answer 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

Answer 4

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

Answer 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

Answer 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

Answer 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)

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

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

Answer 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