My python program won't execute or show anything in the terminal

Question

So I was trying to solve a project Euler question that asks we shoud find the largest prime factor of 600851475143. This is my code:

factors = [i for i in range(1,600851475144) if 600851475143%i is 0]
prime_factors = []
for num in factors:
    factors_of_num = [i for i in range(1, num+1) if num%i is 0]
    if factors_of_num == [1, num]:
        prime_factors.append(num)
print(max(prime_factors))

The issue is that this code won't run for a large number like this. How can \i get this to work?

Answer 1

Your program is executing, but range(1, 600851475144) is just taking a rrrrrrrrrrrrrrrrrrrrrrrreally long time. There are much better ways to get prime factors instead of first checking each number individually whether it is a divisor and then checking which of those are primes.

First, for each pair of divisors p * q = n, either p or q has to be <= sqrt(n), so you'd in fact only have to check the numbers in range(1, 775147) to get one part of those pairs and get the other for free. This alone should be enough to make your program finish in time. But you'd still get all the divisors, and then have to check which of those are prime.

Next, you do not actually have to get all the prime factors of those divisors to determine whether those are prime: You can use any to stop as soon as you find the first non-primitive factor. And here, too, testing up to sqrt(num) is enough. (Also, you could start with the largest divisor, so you can stop the loop as soon as you find the first one that's prime.)

---

Alternatively, as soon as you find a divisor, divide the target number by that divisor until it can not be divided any more, then continue with the new, smaller target number and the next potential divisor. This way, all your divisors are guaranteed to be prime (otherwise the number would already have been reduced by its prime factors), and you will also need much fewer tests (unless the number itself is prime).