# factor.py
# Fig. 17.14 
# input 123456789 or 999999999999 or 111111111111111

def factorsOdd(n):
  if n%2 == 0:
    print("Number must be odd")
    return []

  fs = []
  d = 3
  while d*d <= n: 
    while n == d*int(n/d): 
      fs.append(d)
      n = n//d
    d += 2
  if n > 1:
    fs.append(n)
  return fs


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


if __name__ == "__main__":
  n = int(input("n=? "))
  print("Factors Odd:", factorsOdd(n))
  print("Factors:", factors(n))