recurser

I’ve been slowly working through the Project Euler problems, and came across a prime sieve algorithm for Python , which I’ve modified slightly to return the prime factors of a number. It doesn’t actually work to solve the Project Euler problem in question because it runs out of memory on the range(3,n+1,2) call, but it may come in handy for smaller numbers.

def primeFactors(n): 
	if n==2: return [2]
	elif n<2: return []
	s=range(3,n+1,2)
	mroot = n ** 0.5
	half=(n+1)/2-1
	i=0
	m=3
	while m <= mroot:
		if s[i]:
			j=(m*m-3)/2
			s[j]=0
			while j<half:
				s[j]=0
				j+=m
		i=i+1
		m=2*i+3
	return [2]+[x for x in s if x and n%x==0]