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 | |||||
Guido van Rossum | ec758ea | 1991-06-04 20:36:54 +0000 | [diff] [blame] | 11 | def fact(n): |
Georg Brandl | 22fff43 | 2009-10-27 20:19:02 +0000 | [diff] [blame] | 12 | if n < 1: |
13 | raise ValueError('fact() argument should be >= 1') | ||||
14 | if n == 1: | ||||
15 | return [] # special case | ||||
Tim Peters | e6ddc8b | 2004-07-18 05:56:09 +0000 | [diff] [blame] | 16 | res = [] |
Georg Brandl | 22fff43 | 2009-10-27 20:19:02 +0000 | [diff] [blame] | 17 | # Treat even factors special, so we can use i += 2 later |
18 | while n % 2 == 0: | ||||
Tim Peters | e6ddc8b | 2004-07-18 05:56:09 +0000 | [diff] [blame] | 19 | res.append(2) |
Georg Brandl | 22fff43 | 2009-10-27 20:19:02 +0000 | [diff] [blame] | 20 | n //= 2 |
Tim Peters | e6ddc8b | 2004-07-18 05:56:09 +0000 | [diff] [blame] | 21 | # Try odd numbers up to sqrt(n) |
Georg Brandl | 22fff43 | 2009-10-27 20:19:02 +0000 | [diff] [blame] | 22 | limit = sqrt(n+1) |
Tim Peters | e6ddc8b | 2004-07-18 05:56:09 +0000 | [diff] [blame] | 23 | i = 3 |
24 | while i <= limit: | ||||
Georg Brandl | 22fff43 | 2009-10-27 20:19:02 +0000 | [diff] [blame] | 25 | if n % i == 0: |
Tim Peters | e6ddc8b | 2004-07-18 05:56:09 +0000 | [diff] [blame] | 26 | res.append(i) |
Georg Brandl | 22fff43 | 2009-10-27 20:19:02 +0000 | [diff] [blame] | 27 | n //= i |
Tim Peters | e6ddc8b | 2004-07-18 05:56:09 +0000 | [diff] [blame] | 28 | limit = sqrt(n+1) |
29 | else: | ||||
Georg Brandl | 22fff43 | 2009-10-27 20:19:02 +0000 | [diff] [blame] | 30 | i += 2 |
Tim Peters | e6ddc8b | 2004-07-18 05:56:09 +0000 | [diff] [blame] | 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: |
Georg Brandl | 22fff43 | 2009-10-27 20:19:02 +0000 | [diff] [blame] | 37 | source = sys.argv[1:] |
Tim Peters | e6ddc8b | 2004-07-18 05:56:09 +0000 | [diff] [blame] | 38 | else: |
Georg Brandl | 22fff43 | 2009-10-27 20:19:02 +0000 | [diff] [blame] | 39 | source = iter(input, '') |
40 | for arg in source: | ||||
Tim Peters | e6ddc8b | 2004-07-18 05:56:09 +0000 | [diff] [blame] | 41 | try: |
Georg Brandl | 22fff43 | 2009-10-27 20:19:02 +0000 | [diff] [blame] | 42 | n = int(arg) |
43 | except ValueError: | ||||
44 | print(arg, 'is not an integer') | ||||
45 | else: | ||||
46 | print(n, fact(n)) | ||||
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() |