1
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ Please give examples of numbers handled and result. Did you try to obtain a run time profile? \$\endgroup\$ – greybeard Feb 16 at 22:49
  • \$\begingroup\$ greybeard Well 13195 worked and gave 29. This is my first time using this site, I am not entirely sure what a run time profile is. \$\endgroup\$ – Newbie101 Feb 16 at 22:57
  • \$\begingroup\$ @Newbie101 He wants you to run your code in a profiler to find where to slow spots are. I'm writing a review right now, but always consult a profiler if you're having difficulties finding out why code is slow or taking too much memory. \$\endgroup\$ – Carcigenicate Feb 16 at 22:58
  • \$\begingroup\$ Carcigenicate But what if my program does not finish executing, and it's been over 5 minutes... \$\endgroup\$ – Newbie101 Feb 16 at 23:07
  • \$\begingroup\$ @Newbie101 Profilers can handle that. They watch the program as it runs and keep track of how much time is spent in each function. \$\endgroup\$ – Carcigenicate Feb 16 at 23:08
0
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.