bkula bkula - 7 months ago 15
Python Question

Project Euler Q #3 Python

I'm really trying to improve my math/coding/problem solving skills by working through the Project Euler problems, and I'm a little stuck on question three. The question is "The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?"

And here's my code thus far

import math

def isPrime(n):
if n > 1:
for i in range(2, n):
if n % i == 0:
return False
else:
return True
else:
return False

def highFactor(m):
factors = []
for i in range(2, int(math.sqrt(m))):
if isPrime(i):
if m % i == 0:
factors.append(i)
print max(factors)

highFactor(13195)


So this obviously was testing on the example they gave since I already know the answer should be 29, but when I run the code it gives me 91. What did I do wrong?

Answer

As mentioned in the comments, your function returns True too early - e.g. if a number is not divisble by 2, it does not mean it will not be divisible by any later number in the range(2, n) - consider 51 = 3 * 17 as a counter-example.

Here is the correct version of your algorithm:

def isPrime(n):
    if n > 1:
        for i in range(2, n):
            if n % i == 0:
                return False
       return True
    else:  # if we have a negative number or 0
       return False

As others mentioned, there is a faster way to check whether a number is prime; now your function has complexity of O(n), since you check for all numbers up to n; by observation that n = sqrt(n) * sqrt(n) it is enough to check until sqrt(n) + 1

def isPrime(n):
    if n > 1:
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                return False
        return True
    else:
        return False
Comments