大きな数の因数分解

9182736455463728191
という数を因数分解するように依頼がありました。素数かしら、とか暗号でも解くのかしらと思いましたが、ぜんぜん素数ではなくて、まず23で割れました。
で、解答は
23 * 4093* 8779 * 21649 * 513239
なのですが、云々。
はじめ下のプログラム（factorization, rubyで検索）に9182736455463728191を入れたら、メモリー不足でエラーになってしまいましたので、次に10000までの素数をまず割り出してarrayにして、その中から余りゼロの数を出したら、23、4093、8779の3つの数がヒットして、それで割ったら、11111111111になったのでこれくらいの桁数なら大丈夫だろうと、下記のプログラムで解決、という流れです。

def primes_up_to(n) # calculate all the primes up to the number
  r = (2..n).to_a # convert to an array
  primes =[]
  while r.first**2 < n # up to square root
    primes.push(r.first)
    r.reject! { |i| i % primes.last == 0} # sieve
  end
  primes + r # the rest are primes
end

def factor(n) # factorization in prime numbers
  factors = {}
  for p in primes_up_to((n**0.5).ceil) # up to square root
    while n % p == 0
      factors[p] ? factors[p] += 1: factors[p] = 1 # if exist count up else make one
      n /= p # divide the base
    end
  end 
  factors[n] = 1 if n != 1 # if no primes then n => 1 is the answer
  factors
end

i = 11111111111
p factor(i)

で、{513239=>1, 21649=>1}
となり、ちゃんちゃん。