CODEWITHSUNDEEP
python
bkula
bkula

Reputation: 569

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?

Upvotes: 1

Views: 113

Answers (3)

A. Campbell
A. Campbell

Reputation: 414

As Austin commented isPrime returns true too early. By moving return True outside of the for loop your function will check each number in range(2, n) before confirming that the number is prime.

Say you were to do isPrime(13) which should return True

On the first pass of the for loop if n % i == 0 would be if 13 % 2 == 0 which is False. Because of the else: return True in the for loop the function will return True and terminate.

To solve the issue you could write isPrime() like:

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

Upvotes: 0

jermenkoo
jermenkoo

Reputation: 653

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

Upvotes: 0

cag51
cag51

Reputation: 173

Two issues:

(1) Your isPrime function returns True on the first iteration of the loop. You instead want to finish looping and then return True if you survive the entire loop without ever returning false.

(2) It's possible that an algorithm will have multiple copies of the same prime factor (ie 8 = 2*2*2). You would be better off setting m = m/i and restarting the loop every time. Also, you probably want sqrt(m)+1, since the range function excludes the upper limit.

Upvotes: 1

Related Questions