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 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()