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

user_13172584 0
Viewed 78

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))
python-3.x python
4 Answers

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.

user_130992330

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.

user_131186320

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

user_104132990

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))
user_104132990
Related