Work out largest prime factor of a number

Question

I am trying to get better at problem solving, so I am going through challenges on Project Euler.

Problem:

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

What is the largest prime factor of the number 600851475143 ?

My solution:

My approach to this was the following process:

• Get all factors of the number

• Identify prime factors by looping from 1 up to each factor. If the factor MOD the numbers going up is equal to 0 and the number is not 1 or the number itself, then it is not a prime. Then another for loop goes through each factor again and checks if it is not in the not primes list, hence making it a prime.

• The last item in the primes list gives the biggest prime number

Code:

def get_factors(n):
    factors = []
    for i in range(1,n+1):
        if n % i == 0:
            factors.append(i)

    return factors


def get_prime_factors(factors):
    print(factors)
    primes = []
    not_primes = [1]
    for i in range(len(factors)):
        for k in range(1,factors[i]+1):
            if factors[i] % k == 0 and factors[i] !=1 and k!=1 and k!=factors[i]:
                not_primes.append(factors[i])
    for i in factors:
        if i not in not_primes:
            primes.append(i)
    return primes

def biggest_prime(primes):
    biggest = primes[-1]
    print(biggest)


factors = get_factors(600851475143)
primes = get_prime_factors(factors)
biggest_prime(primes)

Problems with my solution:

It seems like it is too overcomplicated, which is why it can only handle small numbers. The program did not finish executing for the number 600851475143.

What is specifically making my solution so inefficient, is it because I am using too many loops? How can I make it efficient?

Answer 1

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.

Answer 2

There are many questions about Project Euler 3 on this site already. The trick is to pick an algorithm that…

• Reduces n whenever you find a factor, so that you don't need to consider factors anywhere near as large as 600851475143
• Only finds prime factors, and never composite factors

from itertools import chain, count

def biggest_prime_factor(n):
    for f in chain([2], count(3, 2)):
        while n % f == 0:
            n //= f
            if f >= n ** 0.5:
                return f if n == 1 else n

print(biggest_prime_factor(600851475143))