# [PYTHON MATRIX-SIG] Factoring?

**tim@lassi.ece.uiuc.edu
**
tim@lassi.ece.uiuc.edu

*Fri, 16 Aug 1996 10:29:48 -0500*

Here's another factoring routine. It runs pretty fast (under a second
using the profiler for '129753308'), but I have no idea if its very
good algorithymically. I doubt that this is really what you want, but
its yours to play with. I've been tweaking it recently, so if you find
any bugs, let me know. Enjoy.
def factor(n):
"""Return a tuple containing the factors of n.
This is probably not the best way to do this, but hey,
it's simple.
"""
# Take care of special cases.
if n <= 0: raise ValueError
elif n <= 3: return [n]
elif n <= 5: c = arange(2,n+1)
else: # General case.
sr = int(sqrt(n))
c = concatenate((arange(2, n/sr), n/arange(sr,0,-1)))
c = compress(equal(n%c,0), c)
factors = [c[0]]
while len(c) > 1:
c = choose(notEqual(c[1:]%c[0],0), (c[1:]/c[0], c[1:]))
if c[0] != 1:
factors.append(c[0])
return factors
--
-tim
+--------------------------------------------------------------------+
|* Tim Hochberg Ultrahigh Speed Digital Electronics Lab |
*|* tim@lassi.ece.uiuc.edu University of Illinois |
*|* http://dogbert.ece.uiuc.edu/~tim (217) 333-6014 |
*+--------------------------------------------------------------------+
=================
MATRIX-SIG - SIG on Matrix Math for Python
send messages to: matrix-sig@python.org
administrivia to: matrix-sig-request@python.org
=================