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