Prime Factor Decomposition

[mike_w]

The title gives most of it away - what's the quickest way to reduce any number down to its prime factors using a computer?

In case you don't know what prime factor decomposition is:

You can break down any non-prime number into two numbers. If either of those aren't prime, you can break them down into two more numbers each, and so on, until all you're left with is prime factors e.g.

1000 = 10 * 100
10 = 2 * 5, 100 = 2 * 50
So: 1000 = 2 * 5 * 2 * 50
50 = 5 * 10
So: 1000 = 2 * 5 * 2 * 5 * 10
10 = 2 * 5
So: 1000 = 2 * 5 * 2 * 5 * 2 * 5
1000 = 2^3 * 5,^3

I've been using Python, and the best I've come up with is this:

def PrimeFactors(original):
	results = [int(original)]
	factor = 2
	while factor < original:
		if original % factor == 0:
			del results[0]
			results.extend([factor])
			results.extend(PrimeFactors(original / factor))
			return results
		factor = factor + 1
	return results

The basic principle is:
1) Find the first factor by starting with 2 and working upwards
2) Stick the first factor into the list, since it must be prime
3) Find the factors of the second factor using the same method
4) Keep on going until all you're left with are prime factors

However, as you might expect, it gets rather slow once you get onto higher digit numbers. Can anybody think, or know, of a faster method?

Thanks

Mike.

Edit: Oh, I know that Python is slow at this. Is there an easy way of sticking C code into a Python program?