All factors of a given number

user_225727 0
Viewed 30181

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?

math ruby algorithm
11 Answers

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.

user_2569700
Related