[PYTHON MATRIX-SIG] Factoring?

[tim@lassi.ece.uiuc.edu]

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
=================