Home | History | Annotate | Download | only in scripts 
      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()
     50