# factor.py
'''
  input 123456789 or 999999999999 or 
  10967535067
  111111111111111

n=? 111111111111111111111111111111113
1867  in 1.10 secs
11519  in 0.00 secs
141325637  in 11.92 secs
36557580306963713  in 3.83 secs
  
n=? 5166523324060302275610181
141325637  in 14.48 secs
36557580306963713  in 3.91 secs

n=? 280846283204599997
265371653  in 21.95 secs
1058313049  in 0.00 secs

  https://www.numberempire.com/numberfactorizer.php
'''


import math, time
import decimal
from decimal import Decimal as D

def factors(n):
  fs = []
  while n == 2*(n//2): 
    fs.append(2)
    n = n//2
  while n == 3*(n//3): 
    fs.append(3)
    n = n//3
  d = 5
  s = 2
  while d*d <= n: 
    while n == d*(n//d): 
      fs.append(d)
      n = n//d
    d += s
    s = 6-s
  if n > 1:
    fs.append(n)
  return fs

def factorsY(n):
  while n == 2*(n//2): 
    yield 2
    n = n//2
  while n == 3*(n//3): 
    yield 3
    n = n//3
  d = 5
  s = 2
  while d*d <= n: 
    while n == d*(n//d): 
      yield d
      n = n//d
    d += s
    s = 6-s
  if n > 1:
    yield n

def factorsTime(n):
  start = time.time()
  tot = 0
  for f in factorsY(n):
    duration = time.time()-start
    print(f, f" in {duration:.2f} secs")
    tot += duration
    start = time.time()
  print(f"  Total: {tot:.2f} secs")

def factorsD(n):
  decimal.getcontext().prec = 100    # needed for greater accuracy
  dn = D(n)
  fs = []
  while dn == 2*((dn/2).to_integral_value()): 
    fs.append(D(2))
    dn = dn/2
  while dn == 3*((dn/3).to_integral_value()): 
    fs.append(D(3))
    dn = dn/3
  d = D(5)
  s = D(2)
  while d*d <= dn: 
    while dn == d*((dn/d).to_integral_value()): 
      fs.append(d)
      dn = dn/d
    d += s
    s = D(6)-s
  if n > D(1):
    fs.append(dn)
  return fs

if __name__ == "__main__":
  n = int(input("n=? "))
  # start = time.time()
  # print("Factors:", factors(n))
  # print("Factors:", factorsD(n))
  # print(f"in {time.time()-start:.2f} secs")
  factorsTime(n)