Polynomial factorizer using Rational Root Theorem

pfactor.py

from __future__ import division

def gcd(a, b):
	if a == 0:
		return 1
	
	while b != 0:
		t = b
		b = a % b
		a = t
	
	return int(a)

def lgcd(l):
	return reduce(gcd, l)

def factor(n):
	l = []
	if n != 0:
		for i in range(1,n+1):
			if n % i == 0:
				l.append(i)
	elif n == 0:
		l = [0]
	
	return l

def simp(a, b):
	g = gcd(a, b)

	return (int(a/g), int(b/g))

def pls(p, var_string='x'):
	res = ''
	first_pow = len(p) - 1
	for i, coef in enumerate(p):
		power = first_pow - i
		
		if coef:
			if coef < 0:
				sign, coef = ('-' if res else '-'), -coef
			elif coef > 0: # must be true
				sign = ('+' if res else '')

			str_coef = '' if coef == 1 and power != 0 else str(coef)

			if power == 0:
				str_power = ''
			elif power == 1:
				str_power = var_string
			else:
				str_power = var_string + '^' + str(power)

			res += sign + str_coef + str_power 
			
	return res

def sdiv(poly, div):
	res = [poly[0]]+[0]*(len(poly)-1)
	c = -div[1]/div[0]
	
	for i in range(len(poly)-1):
		res[i+1] = poly[i+1] + int(res[i]*c)
	
	r = res.pop(-1)
	
	return (res,r)

def pfactor(p):
	a = p[-1]
	b = p[0]
	
	pf = []
	f = []
	
	for x in factor(abs(a)):
		for y in factor(abs(b)):
			j,k = simp(x,y)
			pf.append((k,-j))
			pf.append((k,j))
	
	pf = list(set(pf))
	
	for d in pf:
		res, r = sdiv(p, d)
		if r == 0:
			f.append(d)
	
	lf = p
	
	for i in f:
		lf, r = sdiv(lf, i)
	
	lf = [int(i/abs(lgcd(lf))) for i in lf]
	
	f.append(lf)
	
	return f

def spfactor(p):
	f = pfactor(p)
	s = ""
	
	for x in f:
		if x != [1]:
			s += "("+pls(x)+")"
	
	return s

#Test cases:

#60,-431,-76,4453,-2350,-8648,2240

#20,-117,-308,2268,-614,-4743,1190

#20,-97,-105,448,60,-317,349,-70

print("Give polynomial as list of coefficients, in order of decreasing exponents.")
l = eval("["+raw_input("Polynomial: ")+"]")

print(spfactor(l))