All factors of a given number

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

Solution 2:

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

Solution 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

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

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