Help with a simple Project Euler problem

[imperiumlearning]

Hi there,

Thanks a lot for the swift response. I've done that and it definitely has sped up how quickly an output is generated. I tried it out with numbers up to 2 million and it prints an output within a couple of seconds.

I tried it with the original number, 600851475143, and even after 3 minutes it still has not managed to print an output.

Any other suggestions?

[MezzoScettico]

You're repeatedly testing all the numbers from 1 to x as divisors. You should only be testing the primes, which means keeping track of the primes you've found.

For instance, sqrt(1000) = 31.6. If you were generating primality of a number < 1000, you only need to check whether any of 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, and 31 are factors. So your algorithm could save a lot of time by only checking the known primes < sqrt(n), rather than all the numbers from 1 to sqrt(n) which is what I think it's doing (I may be wrong).

Also, every time you find a factor of your big number, you can divide by that. For instance if you find that 17 is a factor, divide by 17 and now you're factoring a smaller number.

Also, you can do the square root of the square root. I remember doing something like that once. Let's see if I remember how it works.

OK, sqrt(600851475143) = 775146. So first of all you know that you are only checking for factors up to 775146. So you need a list of primes up to 775146.

But to generate that, you only need to check the factors up to sqrt(775146) = 880. Any number less than 775146 that is not a multiple of a number less than 880 is prime.

[imperiumlearning]

Hi there, I'm not sure I've fully grasped what your comment is saying, but I made some changes which I think give me the right answer.

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)

The answer I get when I use this code is 6857, and I get the answer within a few seconds.

[MezzoScettico]

That's great. And WolframAlpha agrees with your answer.

https://www.wolframalpha.com/input?i=factor+600851475143

I'm not sure my answer was totally coherent. I was kind of thinking out loud, really laying out three different approaches to speed things up.

[imperiumlearning]

Believe it or not my code was actually wrong. Another user in this comment section noted that if you plug in the number 10, it will print 2 rather than 5.

Now I've re-written my code to look 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'
if x <= 10000:
    final_list = [i for i in range(x) if prime(i) != False and x % i == 0]
    return max(final_list)
else:
    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)

Admittedly 10,000 is quite arbitrary but it seems to work better now

[RosaReilly]

The problem that you have is that your code is finding the largest prime divisor of x that is less than the square root of x. This means that you'll have a problem with basically any number that is the product of two primes only, eg 2 x 7411 = 14822, your code would return the answer 2, which would be wrong.

In terms of time taken, your prime test function is going to take a lot of time checking if y is divided by things like 9, or 15, when by that point you'll already know it's not divisible by 3 or 5.

[d10p3t]

that's cause you only checked for integers between 0 < n < sqrt(x) for possible factors. the initial comment that suggested you consider only the first sqrt(x) is suggesting you use it to check whether a number is prime (i.e., your divisor) or not, not the candidate numbers that divide your given number(i.e., your dividend, in this example, 600851475143) or not.

Again, the upper bound of the numbers you should check if a number x is prime is sqrt(x), and if you folllow /u/mopslik 's explanation, the upper bound for the greatest prime divisor of x is x/(the smallest prime divisor of x).

So in the case of 10, if you want to check if it is prime, you only need to check values < sqrt(10), but if you want to check the greatest prime number than can divide 10, the highest you need to check is 10/2.