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:
  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
  35 def 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
  48 if __name__ == "__main__":
  49     main()