Project Euler - Problem #3

Largest Prime Factor

The prime factors of 13195 are:

5, 7, 13, 29

What is the largest prime factor of the number 600851475143?

Well, I did not expect to get defeated as early as problem #3, although I partially made some progress...

x = 13195
vec = []
for i in range(1,x):
    if x % i == 0:
        vec.append(i)
print(vec)

[1, 5, 7, 13, 29, 35, 65, 91, 145, 203, 377, 455, 1015, 1885, 2639]

This was my partial solution, yet it still doesn't competely solve the question. As we can see, the script print out a list of divisors for the number x. Following through my idea implementation, we can further eliminate the *non-prime* elements of the list, then we're done.

Essentially, I got stuck after this step and went on to look up for solutions from the internet. Here was what I found that elegantly cracked the question. Code below

# Main function
def prime_factors(n):
    factors = []
    divisor = 2
    while n > 1:
        while n % divisor == 0:
            factors.append(divisor)
            n //= divisor
        divisor += 1
    return factors

Code description

This is essentially a prime factor decomposition problem, as one may just extract the list of prime factors that together make up the original number by multiplication.

In the code above, you start with a divisor of 2, then entering the while loop:

• for as long as n not equal 1, the loop continues.
• for as long as n divisible by divisor, then collect that value and add to the prime list.
• Reduce n by divisor. (note the integer product)
• (then check again if n is still divisible by divisor, this is to make sure repeated values of divisor within the main number)
• If n is no longer divisible by divisor then increase divisor value by 1. This step will make the loop to collect all prime numbers from lowest to highest order, until it matches the final largest prime factor that is divisible by n, then n will become 1, then the loop terminates.

It took me a while to fully understand what this function does, but once I laid out all the steps as above, it's clear that it's a beautiful solution. To this problem, although I did not manage to come up with my own answer, I still finally learned a lot about the use of while loop and more importantly, the necessity of mathematic thinking before even begin to implement it in code.

# So here is the answer, finally
x = 600851475143
print(prime_factors(x))

[71, 839, 1471, 6857]