# Find all prime factors of a number.
 
def prime_factors(n)
  r = []
  u = 101
  i = 2
  while i*i <= n
    c = 0
    while n % i == 0
      n /= i
      c += 1
    end
    if c != 0
      r << [i, c]
    end
    # 1224..24
    # (Idk if this is any faster than just incrementing by one)
    d, u = (u * 10).divmod(825)
    i += d
  end
  r << [n, 1] if n > 1
  r
end
 
# Test.
 
10.times do |n|
  p prime_factors(n)
end
p prime_factors(2**31-1)
p prime_factors(2**31)
p prime_factors(3**3*5**5)
p prime_factors(2*3*5*7*11*13*17*19)
p prime_factors(70) # Problem that prompted this.

IyBGaW5kIGFsbCBwcmltZSBmYWN0b3JzIG9mIGEgbnVtYmVyLgoKZGVmIHByaW1lX2ZhY3RvcnMobikKICByID0gW10KICB1ID0gMTAxCiAgaSA9IDIKICB3aGlsZSBpKmkgPD0gbgogICAgYyA9IDAKICAgIHdoaWxlIG4gJSBpID09IDAKICAgICAgbiAvPSBpCiAgICAgIGMgKz0gMQogICAgZW5kCiAgICBpZiBjICE9IDAKICAgICAgciA8PCBbaSwgY10KICAgIGVuZAogICAgIyAxMjI0Li4yNAogICAgIyAoSWRrIGlmIHRoaXMgaXMgYW55IGZhc3RlciB0aGFuIGp1c3QgaW5jcmVtZW50aW5nIGJ5IG9uZSkKICAgIGQsIHUgPSAodSAqIDEwKS5kaXZtb2QoODI1KQogICAgaSArPSBkCiAgZW5kCiAgciA8PCBbbiwgMV0gaWYgbiA+IDEKICByCmVuZAoKIyBUZXN0LgoKMTAudGltZXMgZG8gfG58CiAgcCBwcmltZV9mYWN0b3JzKG4pCmVuZApwIHByaW1lX2ZhY3RvcnMoMioqMzEtMSkKcCBwcmltZV9mYWN0b3JzKDIqKjMxKQpwIHByaW1lX2ZhY3RvcnMoMyoqMyo1Kio1KQpwIHByaW1lX2ZhY3RvcnMoMiozKjUqNyoxMSoxMyoxNyoxOSkKcCBwcmltZV9mYWN0b3JzKDcwKSAjIFByb2JsZW0gdGhhdCBwcm9tcHRlZCB0aGlzLg==