Finding all prime factors of a number

I have a function that is able to return the factors of a number that are prime.

For example: The prime factors of 13195 are 5, 7, 13 and 29.

The function works great, and I was even able to improve it by dividing by just prime numbers instead of all numbers. The problem is it still isn't efficient enough because at 100,000,000 the program takes 10 seconds to finish and the number I need to run through this is 600,851,475,143 which will take more than 6000 times longer to finish.

In the spirit of the challenge, I don't want to be given the answer, but some guidance.

There are also issues with just how large the number is. If I use xrange() it will still give me an overflow error but this isn't a huge problem (I can google answers for that).

def getPrimesM(integer, start=4):
  primes = [2,3]
  for num in range(start, integer):
    if integer % num == 0:
      for i, prime in enumerate(primes):
        if num % prime == 0:
          break
        if i >= len(primes) - 1:
          primes.append(num)

  return primes

Your function will always report that 2 and 3 are prime factors of your number.

Trial division is a fine strategy for this problem, and it can find the factors of 600,851,475,143 quite quickly. You have to do it smartly, though. If your main loop is for num in range(start, integer): … or for num in xrange(start, integer): …, and there's no break for that loop, then you're going to be counting up to 600 billion.

Another important detail is that when you find a factor, you should use that information to reduce the integer as much as possible. If you do it correctly, then you won't need that inner loop for primality testing anymore.

Another useful tip is to test candidates 2, 3, 5, 7, 9, 11, 13, … — in other words, 2 followed by just the odd numbers. You can write that as

from itertools import chain, count

for num in chain([2], count(3, 2)):
    …

StackExchange Code Review Q#92704, answer score: 4