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
if n > 1:
for i in range(2, n):
if n % i == 0:
factors = 
for i in range(2, int(math.sqrt(m))):
if m % i == 0:
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