Is this a good Ruby implementation of Prime Factorization? I'm doing some practice problems on Khan Academy. The current one is Prime factorization. I came up with this:

require 'prime'

def prime_factorization(n, primes = nil)
  return [n] if Prime.prime? n

  primes ||= Prime.take_while { |p| p &lt; n/2 }
  factorization = []
  prime = primes.detect { |p| n % p == 0 }
  factor = n / prime
  factorization &lt;&lt; prime

  if Prime.prime? factor
    factorization &lt;&lt; factor
  else
    factorization += prime_factorization factor, primes
  end

  factorization
end


The benchmarks for this are:


                            user       system     total       real
prime factorization of 75:  0.000000   0.000000   0.000000 (  0.000129)
prime factorization of 750:  0.000000   0.000000   0.000000 (  0.000241)
prime factorization of 4202:  0.000000   0.000000   0.000000 (  0.000498)
prime factorization of 39450:  0.010000   0.000000   0.010000 (  0.003061)
prime factorization of 460522:  0.050000   0.000000   0.050000 (  0.057704)




What is the big O notation for this method?
How does this algorithm compare to optimal prime factor algorithms in terms of complexity/performance?
Is recursion a good way to solve this problem?
How could it be improved?
Is this a stupid question?
Reinventing the wheel

There is an easier solution, considering that you are using the Prime class, which already has a Prime.prime_division() method that does almost the same thing.  The only difference is the output format: your prime_factorization(360) would output [2, 2, 2, 3, 3, 5], whereas Prime.prime_division(360) would output [[2, 3], [3, 2], [5, 1]].  It's just a matter of converting the output by repeating each prime factor the specified number of times.

require 'prime'

def prime_factorization(n)
  Prime.prime_division(n).flat_map { |factor, power| [factor] * power }
end


(Thanks to @Flambino and @tokland for simplifying the transformation.)

Critique

You've asked some very interesting questions.

The big-O complexity of this method is not at all simple to analyze.  You call methods such as Prime.prime?() that in turn make use of a generator.  Then you also call Prime.take_while(), Prime.prime?(factor).  On top of that, there's recursion.   All I will say, though, is that the method can be very inefficient.

The initial call to prime?(n) already does a trial division that resembles the kind of work your method will perform.  Calling prime? is altogether redundant — see Simplification 1 below.

The call to primes ||= Prime.take_while { |p| p &lt; n / 2 } can also be very inefficient.  For example, to calculate prime_factorization(360), you would be asking it to generate primes up to 179, even though no prime factor above 5 exists.

Ruby provides an Integer.divmod() function that lets you avoid having to recalculate n / p immediately after having ascertained n % p == 0.

When you recurse, you test every prime number all over again, starting with 2, 3, 5, ….  Rather, you want to be able to continue by testing the same prime factor that succeeded.

Simplification 1

Assuming that you are deliberately reinventing-the-wheel, you can still improve your method in several ways:


Eliminate calls to prime?
Make early termination work by removing take_while in favour of a break
Use divmod
Replace recursion with looping
Just yield factors as you detect them.  Let to_enum and to_a take care of appending results to the array.




def prime_factorization(n)
  def factor_generator(n)
    Prime.instance.each do |p|
      break if p &gt; n
      begin
        div, mod = n.divmod(p)
        if mod == 0
          yield p
          n = div
        end
      end while mod == 0
    end
  end

  to_enum(:factor_generator, n).to_a
end


Simplification 2

The implementation above is still inefficient, since there is already primality testing hidden inside Prime.instance.each.  To avoid duplication of effort between your code and the Prime class, you should be able to test any increasing sequence of numbers that is not obviously composite.

def prime_factorization(n)
  def factor_generator(n)
    for prime_candidate in Prime::Generator23.new
      break if prime_candidate &gt; n
      begin
        div, mod = n.divmod(prime_candidate)
        if mod == 0
          yield prime_candidate
          n = div
        end
      end while mod == 0
    end
  end

  to_enum(:factor_generator, n).to_a
end