1 #! /usr/bin/env python

     2 

     3 # Factorize numbers.

     4 # The algorithm is not efficient, but easy to understand.

     5 # If there are large factors, it will take forever to find them,

     6 # because we try all odd numbers between 3 and sqrt(n)...

     7 

     8 import sys

     9 from math import sqrt

    10 

    11 def fact(n):

    12     if n < 1: raise ValueError # fact() argument should be >= 1

    13     if n == 1: return []    # special case

    14     res = []

    15     # Treat even factors special, so we can use i = i+2 later

    16     while n%2 == 0:

    17         res.append(2)

    18         n = n//2

    19     # Try odd numbers up to sqrt(n)

    20     limit = sqrt(float(n+1))

    21     i = 3

    22     while i <= limit:

    23         if n%i == 0:

    24             res.append(i)

    25             n = n//i

    26             limit = sqrt(n+1)

    27         else:

    28             i = i+2

    29     if n != 1:

    30         res.append(n)

    31     return res

    32 

    33 def main():

    34     if len(sys.argv) > 1:

    35         for arg in sys.argv[1:]:

    36             n = eval(arg)

    37             print n, fact(n)

    38     else:

    39         try:

    40             while 1:

    41                 n = input()

    42                 print n, fact(n)

    43         except EOFError:

    44             pass

    45 

    46 if __name__ == "__main__":

    47     main()