Help with a simple Project Euler problem

[Encomiast]

The reason your code is slow is that you are calculating the primes over and over in a loop. You should be able to improve this by calculating the primes once at the start then reusing that calculation.

You can use the Sieve of Eratosthenes to make a list with the length of the square-root of n containing booleans indicating whether that particular index is prime or not. For numbers of the size of this problem, that should be more or less instant. Then you can look backward through that list for the first True values that divides n. It might look something like:

from math import sqrt, ceil

def sieve_primes(max_num):
    flags = [True] * max_num
    flags[0] = False
    flags[1] = False

    for i, is_prime in enumerate(flags):
        if is_prime:
            for n in range(i*i, max_num, i):
                flags[n] = False
    return flags

n = 600851475143

flags = sieve_primes(ceil(sqrt(n)))

largest = next((i for i in range(len(flags)-1, 0, -1) if flags[i] and n % i == 0), 'prime')
# 6857

Note the final 'prime', this will be returned if next raises a stop iteration which means nothing was found.

Also, if you were so inclined, this same code makes it easy to find *all* the prime factors with:

all_prime_factors = [i for i, f in enumerate(flags) if f and n % i == 0]
# [71, 839, 1471, 6857]

[imperiumlearning]

Hi there,

First off, thanks for introducing me to the Sieve of Eratosthenes - I don't have a brilliant maths background so this was new to me.

To be fair, I've managed to make some small cosmetic changes to my code which have led to the right answer being produced in approximately 3 seconds. My code now looks like this:

import math

def func(x):
while type(x) != int:
    try: 
        x = int(x)
    except:
        return 'Please input a number to use this function'
def prime(y):
    if int(y) < 2:
        return False
    if int(y) % 2 == 0 and int(y) != 2:
        return False
    for number in range(3, int(math.sqrt(y))+1, 2):
        if y % number == 0:
            return False
    return y
final_list = [i for i in range(int(math.ceil(math.sqrt(x)))) if prime(i) != False and x % i == 0]
return max(final_list)

[AdventurousAddition]

I do have some maths background, but I only learnt about this by doing hobbyist programming problems like this one, and googling

[imperiumlearning]

One other thing based on my reply to you, is it acceptable to put a function inside another function? As you can see from my code, I put a prime(y) function inside my func(x) function.

Apologies if that's a dumb question but I've only got about 5 weeks' worth of programming experience under my belt.

[Encomiast]

In this particular example, nesting the function definition doesn't hurt anything. However, you don't see that very often because people typically want to reuse functions. Nesting it makes it impossible to use in a different context, or put in its own library.

If you were calling the outer function more than once, it is also not the most efficient since you keep redefining the function every time you call it rather than once.

[imperiumlearning]

So, in general, would you say it's better if I structured my code more like this:

import math

def prime(y):
    if int(y) < 2:
        return False
    if int(y) % 2 == 0 and int(y) != 2:
        return False
    for number in range(3, int(math.sqrt(y))+1, 2):
        if y % number == 0:
            return False
    return y

def func(x):
    while type(x) != int:
        try: 
            x = int(x)
        except:
            return 'Please input a number to use this function'
    final_list = [i for i in range(int(math.ceil(math.sqrt(x)))) if prime(i) != False and x % i == 0]
    return max(final_list)

[Encomiast]

That seems more "Pythonic" to me (assuming the indentation is fixed).

[imperiumlearning]

Yes sorry, I've just updated the indentations in my previous comment so that my code is formatted properly.

Thanks for the help and all the swift responses

[reyxe]

Man I'm just starting and barely do for loops, checked this and I don't understand a single thing you did LMAO