There's a few things that can be improved.
get_factors can be a generator:
def lazy_get_factors(n): for i in range(1,n+1): if n % i == 0: yield i
This means all the factors don't need to be entirely found ahead of time. This doesn't have much in the way of gains for you right now since you're relying on the length of the list of factors which means you'd have to realize the entire list anyways, but if you change your algorithm, it may be beneficial. If you substitute this into your code (which isn't necessarily beneficial in the current state), make sure to force the factors into a list first:
factors = list(get_factors(600851475143))
Although this defeats the purpose of making it lazy, it's necessary with your current algorithm.
The only purpose of not_primes is to maintain "seen" membership. Right now, you're using a list to track membership, which is a bad idea since it means in will need to search the entirety of not_primes to see if it contains an element. Use a set here instead:
not_primes = {1} # A set . . . not_primes.add(factors[i]) # add instead of append
This instantly makes in much faster. The code will no longer slow down as not_primes grows.
The bottom bit of get_prime_factors can be written simply as:
return [fact for fact in factors if fact not in not_primes]
And then you can get rid of the primes list at the top.
get_prime_factors is far too big and encompassing too much. It's difficult to look at any single piece of it and easily tell what's going on. You should break the function up into multiple pieces. See my alternate solution below for an example of how much more readable that can make code.
Here's an entirely different take on it. It uses quite a lot of generators. It's able to find the largest factor nearly instantly. See the comments in the code:
from math import sqrt # Lazily checks all the possible factors of n, yielding factors as it finds them # Ignores 1 as a factor since that's a given def factors_of(n): # Sqrt is used here as an optimization for fact in range(2, int(sqrt(n) + 2)): # Uncomment the below line to see how it only does as much work as needed # print(fact) if n % fact == 0: yield fact def is_prime(n): # This is cheap. It doesn't do any work up front. # It's only used here to see if the number has 0 or greater than 0 factors factors = factors_of(n) # An ugly way to check if a generator has any elements # WARNING: Consumes the first element if it exists! return n == 2 or \ not next(factors, None) def prime_factors_of(n): factors = factors_of(n) return (fact for fact in factors if is_prime(fact)) def largest_prime_factor_of(n): prime_factors = prime_factors_of(n) # "Apply" the prime factors to max # Necessary since max is var-arg return max(*prime_factors)
See here for an explanation of the next(factors, None) hack.
Note that not everything here is optimal. The fact that factors_of doesn't return 1 is stupid, but if it did return 1, that would complicate is_prime as then I'd have to check if it contains greater than 1. I tried to keep it simple and brief.
And arguably, prime_factors_of and largest_prime_factor_of don't need the factors and prime_factors variables. The whole of those functions could be on one line. I like having everything spaced out a bit though.
