Demo/scripts/fact.py

   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 error = 'fact.error'            # exception
  12
  13 def fact(n):
  14         if n < 1: raise error   # fact() argument should be >= 1
  15         if n == 1: return []    # special case
  16         res = []
  17         # Treat even factors special, so we can use i = i+2 later
  18         while n%2 == 0:
  19                 res.append(2)
  20                 n = n/2
  21         # Try odd numbers up to sqrt(n)
  22         limit = sqrt(float(n+1))
  23         i = 3
  24         while i <= limit:
  25                 if n%i == 0:
  26                         res.append(i)
  27                         n = n/i
  28                         limit = sqrt(n+1)
  29                 else:
  30                         i = i+2
  31         if n != 1:
  32                 res.append(n)
  33         return res
  34
  35 def main():
  36         if len(sys.argv) > 1:
  37                 for arg in sys.argv[1:]:
  38                         n = eval(arg)
  39                         print n, fact(n)
  40         else:
  41                 try:
  42                         while 1:
  43                                 n = input()
  44                                 print n, fact(n)
  45                 except EOFError:
  46                         pass
  47
  48 main()