Guido van Rossum | f06ee5f | 1996-11-27 19:52:01 +0000 | [diff] [blame] | 1 | #! /usr/bin/env python |
Guido van Rossum | ec758ea | 1991-06-04 20:36:54 +0000 | [diff] [blame] | 2 | |
Guido van Rossum | 1c8230b | 1991-12-18 13:45:17 +0000 | [diff] [blame] | 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)... |
Guido van Rossum | ec758ea | 1991-06-04 20:36:54 +0000 | [diff] [blame] | 7 | |
| 8 | import sys |
| 9 | from math import sqrt |
| 10 | |
Tim Peters | e6ddc8b | 2004-07-18 05:56:09 +0000 | [diff] [blame] | 11 | error = 'fact.error' # exception |
Guido van Rossum | ec758ea | 1991-06-04 20:36:54 +0000 | [diff] [blame] | 12 | |
| 13 | def fact(n): |
Tim Peters | e6ddc8b | 2004-07-18 05:56:09 +0000 | [diff] [blame] | 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 |
Guido van Rossum | ec758ea | 1991-06-04 20:36:54 +0000 | [diff] [blame] | 34 | |
| 35 | def main(): |
Tim Peters | e6ddc8b | 2004-07-18 05:56:09 +0000 | [diff] [blame] | 36 | if len(sys.argv) > 1: |
| 37 | for arg in sys.argv[1:]: |
| 38 | n = eval(arg) |
Collin Winter | 6f2df4d | 2007-07-17 20:59:35 +0000 | [diff] [blame^] | 39 | print(n, fact(n)) |
Tim Peters | e6ddc8b | 2004-07-18 05:56:09 +0000 | [diff] [blame] | 40 | else: |
| 41 | try: |
| 42 | while 1: |
Collin Winter | 6f2df4d | 2007-07-17 20:59:35 +0000 | [diff] [blame^] | 43 | n = eval(input()) |
| 44 | print(n, fact(n)) |
Tim Peters | e6ddc8b | 2004-07-18 05:56:09 +0000 | [diff] [blame] | 45 | except EOFError: |
| 46 | pass |
Guido van Rossum | ec758ea | 1991-06-04 20:36:54 +0000 | [diff] [blame] | 47 | |
Johannes Gijsbers | 7a8c43e | 2004-09-11 16:34:35 +0000 | [diff] [blame] | 48 | if __name__ == "__main__": |
| 49 | main() |