Project Euler - Problem 87

Hi everyone, in today's blog post I wanted to share how I completed problem 87 from project euler as I found it really interesting :)

I knew in order to do this I would have to have a list of all the prime numbers up to the square root of 50 million, as any number above the square root would be a repeated factor. As I began researching how to solve this problem I came across the ancient greek algorithm the sieve of Eratosthenes. The code works by eliminating the multiples of all prime numbers and marking them as non prime.

            def sieve_of_eratosthenes(limit):
                is_prime = [True] * (limit + 1)
                is_prime[0], is_prime[1] = False, False  
                for start in range(2, int(limit**0.5) + 1):
                    if is_prime[start]:
                        for multiple in range(start*start, limit + 1, start):
                            is_prime[multiple] = False
                return [num for num, prime in enumerate(is_prime) if prime]
        

Now, the next step was to create 3 loops each of which iterate through the primes and then add the square, cube and fourth power of each to a set sums.

            for sq in primes:
                for cu in primes:
                    if sq**2 + cu**3 >= max:
                        break
                    for fo in primes:
                        sum = sq**2 + cu**3 + fo**4
                        if sum < max:
                            sums.add(sum)
        

The if statement on line 3 ensures the square number + the cube number is not larger than the max value, as if it is then it will be pointless calculating the fourth power number.

The time complexity of the first function sieve of ertosthenes is O(n log log n), and for the main nested for loops it is O((limit/log(limit)³))

The full code can be viewed on github here, thank you for reading! :)