bkula - 1 year ago 35

Python Question

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
```

Source (Stackoverflow)