Guido van Rossum | ec758ea | 1991-06-04 20:36:54 +0000 | [diff] [blame] | 1 | #! /usr/local/python |
| 2 | |
| 3 | # Factorize numbers, slowly. |
| 4 | # This version uses plain integers and is thus limited to 2**31-1. |
| 5 | |
| 6 | import sys |
| 7 | from math import sqrt |
| 8 | |
| 9 | error = 'fact.error' # exception |
| 10 | |
| 11 | def fact(n): |
| 12 | if n < 1: raise error # 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 = int(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 = int(sqrt(float(n+1))) |
| 27 | else: |
| 28 | i = i+2 |
| 29 | res.append(n) |
| 30 | return res |
| 31 | |
| 32 | def main(): |
| 33 | if len(sys.argv) > 1: |
| 34 | for arg in sys.argv[1:]: |
| 35 | n = int(eval(arg)) |
| 36 | print n, fact(n) |
| 37 | else: |
| 38 | try: |
| 39 | while 1: |
| 40 | n = int(input()) |
| 41 | print n, fact(n) |
| 42 | except EOFError: |
| 43 | pass |
| 44 | |
| 45 | main() |