blob: c030187e7b0ce90e6dbff4ad21ec40b6ea396bc8 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
#! /usr/bin/env python
# Factorize numbers.
# The algorithm is not efficient, but easy to understand.
# If there are large factors, it will take forever to find them,
# because we try all odd numbers between 3 and sqrt(n)...
import sys
from math import sqrt
def fact(n):
if n < 1: raise ValueError # fact() argument should be >= 1
if n == 1: return [] # special case
res = []
# Treat even factors special, so we can use i = i+2 later
while n%2 == 0:
res.append(2)
n = n//2
# Try odd numbers up to sqrt(n)
limit = sqrt(float(n+1))
i = 3
while i <= limit:
if n%i == 0:
res.append(i)
n = n//i
limit = sqrt(n+1)
else:
i = i+2
if n != 1:
res.append(n)
return res
def main():
if len(sys.argv) > 1:
for arg in sys.argv[1:]:
n = eval(arg)
print n, fact(n)
else:
try:
while 1:
n = input()
print n, fact(n)
except EOFError:
pass
if __name__ == "__main__":
main()
|
