module PrimeFactor
  def self.new
    @memoized = {}

    Hash.new do |h, index|
      @memoized[index] ||= memoize(h, index)
      h[index] = @memoized[index]
    end
  end

  def self.memoize(h, number)
    divisor = 2
    while divisor < number
      while number % divisor == 0
        number = number / divisor
        return [divisor] + h[number]
      end
      divisor = divisor + 1
    end
    return [number] if number > 1
    return []
  end
end

describe PrimeFactor do
  it "factors 1 through 9" do
    @factors = PrimeFactor.new

    (1..9).each { |number| @factors[number] }

    @factors.should == {
      1 => [],
      2 => [2],
      3 => [3],
      4 => [2, 2],
      5 => [5],
      6 => [2, 3],
      7 => [7],
      8 => [2, 2, 2],
      9 => [3, 3]
    }
  end
end