Function doesn't return anything after giving a big number as an argument

Question

I'm learning Python by doing Project Euler questions and am stuck on Problem #3.

I think I've found a solution that works, but when inserting the large number 600851475143 it just doesn't return anything. I believe that it just loads and loads cause even with 6008514 it takes 10 secs to return the answer.

# What is the largest prime factor of the number x?
import math

def isPrime(x):
    try:
        sqr = math.sqrt(x)
        if x == 0 or x == 1:
            return 0

        for n in range (2 , int(sqr)+1):
            if x % n == 0:
                return 0
        return 1
    except:
        return 'Give positive numbers.'

def largestPrimeFactor(x):
    if isPrime(x) == 1:
        return 'This number is prime.'
    else:
        largest = -1
        mid = x/2
        for n in range(2,int(mid)+1):
            if isPrime(n):
                if x % n == 0:
                    largest = n

        if largest == -1:
            return 'Enter numbers above 1.'
        else:            
            return largest

print(largestPrimeFactor(600851475143))

I suspect it just hasn't finished executing. I just ran this and it's still running after 5 minutes. — Sam Morgan, Mar 31 '20 at 17:24
Yeah, this quickly overran my system resources. I'll take a look and see if I can make it more efficient. — Sam Morgan, Mar 31 '20 at 17:26
damn, does this happen often? also wym it overran your system resources? @SamMorgan — markajino, Mar 31 '20 at 17:26
Nope. You're trying to do something extremely CPU intensive. Try starting with a much smaller input number and see what sort of output you get. Also, add a print statement in each loop so you can see how many calculations are actually being performed. Something like `print(f"isPrime {n}")` and `print(f"largestPrimeFactor {n}")` — Sam Morgan, Mar 31 '20 at 17:29
Project Euler often has questions that seem trivial at first but require a better algorithm for certain values. Take a look at https://stackoverflow.com/questions/23287/algorithm-to-find-largest-prime-factor-of-a-number for some of the algorithms that you can implement. — Chrispresso, Mar 31 '20 at 17:35
Also, this script is uninterruptable since you're using a bare except in `isPrime()` (catches `KeyboardInterrupt`). Never, ever use a bare except, even in testing. In this case, use `except TypeError`. — Sam Morgan, Mar 31 '20 at 17:39
I didn't test the code provided here, but for the record a naive solution (20 lines) can solve the problem in less than 50ms. — Neven V., Mar 31 '20 at 17:47

score 2 · Answer 1 · edited Mar 31 '20 at 17:57

This code should work:

    import math

    def isPrime(x):
        try:
            sqr = math.sqrt(x)
            if x == 0 or x == 1:
                return 0
            n = 2
            highest = x
            while n < highest:
                if x%n ==0:
                    return 0
                highest = x/ n
                n +=1
            return 1
        except:
            return 'Give positive numbers.'

    def largestPrimeFactor(x):
        if isPrime(x) == 1:
            return 'This number is prime.'
        n = 2
        highest = x
        largest = 1
        while n < highest:
            if x%n == 0:
                if isPrime(n):
                    largest = n
            highest = x/n
            n +=1
        return largest


    print(largestPrimeFactor(600851475143))

I made an optimization: you check if every number is a factor of x while if for example 2 is not a factor of x for sure the maximum factor of x can be x/2. Hence if n is not a factor of x the maximum possible factor of x can just be x/n.

i really liked your explanation _Hence if n is not a factor of x the maximum possible factor of x can just be x/n._ Thanks! — markajino, Mar 31 '20 at 18:28

score 2 · Answer 2 · answered Mar 31 '20 at 17:58

2

The code for large numbers just takes really long time, as pointed out by comments. I report other bugs.

Bug 1. Inappropriate use of try/except clause. It is recommended that try contains a single command and except catches the error. PEP8 also recommends specifying the type of error. Moreover, for your function, the error is never raised.

Bug 2. Redundancy. If x is not prime, you call isPrime for each value (let's call it i) from 2 to x/2. isPrime cycles for each number from 2 to sqrt(i). Therefore, isPrime(i) takes O(sqrt(i)) time, and we call it for i from 2 to x/2. Roughly, its running time is about O(x^(3/2)). Even if don't know a more optimal approach, this approach asks for memoization.

answered Mar 31 '20 at 17:58

Kate Melnykova

1,863
1
5
17

Thanks for your response,i don't get what you mean in the Bug 3).I've inserted x/2 in to mid variable so i'm not checkin any number up to X.About bug 2) yeah, i don't know yet the must and must nots, i'll check it out.Last, about Bug1) it doesn't return an error..it says that it is a prime number – markajino Mar 31 '20 at 18:06
Yes, original bug1 was my mistake. Sorry. In what is currently bug 2, a constant factor is dropped in the big O notation. – Kate Melnykova Mar 31 '20 at 18:08

score 1 · Accepted Answer · answered Mar 31 '20 at 18:47

i have another way:

def Largest_Prime_Factor(n):
    prime_factor = 1
    i = 2

    while i <= n / i:
        if n % i == 0:
            prime_factor = i
            n /= i
        else:
            i += 1

    if prime_factor < n:
        prime_factor = n

    return prime_factor

it faster than previous

score 0 · Answer 4 · answered Mar 31 '20 at 17:42

0

try it:

import math       

def maxPrimeFactors (n): 


    maxPrime = -1


    while n % 2 == 0: 
        maxPrime = 2
        n >>= 1        

    for i in range(3, int(math.sqrt(n)) + 1, 2): 
        while n % i == 0: 
            maxPrime = i 
            n = n / i 


    if n > 2: 
        maxPrime = n 

    return int(maxPrime)      


n = 600851475143
print(maxPrimeFactors(n))

answered Mar 31 '20 at 17:42

Jasar Orion

626
7
26

Thanks for your reply, i like your method althought i can't understand why in the for loop you write: n = n / i. What does it do? – markajino Mar 31 '20 at 18:22
I believe your _form loop_ is wrong, cause you're mixing odd numbers with prime.Your incremation by 2 gives odd values up until the square(n).But not all odds are primes too – markajino Mar 31 '20 at 18:44

Function doesn't return anything after giving a big number as an argument

4 Answers4