PYTHON   27
fact
Guest on 10th February 2023 01:52:17 AM


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

Login or Register to edit or fork this paste. It's free.