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
8import sys
9from math import sqrt
10
11def fact(n):
12    if n < 1:
13        raise ValueError('fact() argument should be >= 1')
14    if n == 1:
15        return []  # special case
16    res = []
17    # Treat even factors special, so we can use i += 2 later
18    while n % 2 == 0:
19        res.append(2)
20        n //= 2
21    # Try odd numbers up to sqrt(n)
22    limit = sqrt(n+1)
23    i = 3
24    while i <= limit:
25        if n % i == 0:
26            res.append(i)
27            n //= i
28            limit = sqrt(n+1)
29        else:
30            i += 2
31    if n != 1:
32        res.append(n)
33    return res
34
35def main():
36    if len(sys.argv) > 1:
37        source = sys.argv[1:]
38    else:
39        source = iter(raw_input, '')
40    for arg in source:
41        try:
42            n = int(arg)
43        except ValueError:
44            print arg, 'is not an integer'
45        else:
46            print n, fact(n)
47
48if __name__ == "__main__":
49    main()
50