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