Prime number calculator in Python 3.4.1

I have only been coding for a short time and I have written these two functions and am looking to optimise them. If anyone could point out things that could be done better it would be much appreciated.

Please Note:

This code has been reviewed/improved using the suggestions below, take a look:

# Python 3.4.1
# Function to check if a number is prime

# Takes integer, returns the factors
def findFactors(num):
# Create variable to hold the factors and add 1 and itself (all numbers have these factors)
factors = [1, num]

# For each possible factor
for i in range(2, int(num/4) + 3):
# Check that it is a factor and that the factor and its corresponding factor are not already in the list
if num % i == 0 and i not in factors and int(num/i) not in factors:
# Add it and its corresponding factor to the list
factors.append(i)
factors.append(int(num/i))

return factors

# Takes an integer, returns true or false
def isPrime(number):
number = int(number)

# Check if the only factors are 1 and itself and it is greater than 1
if len(findFactors(number)) == 2 and number > 1:
return True

return False


2 Answers

Style

Python has a style guide called PEP 8 which is definitly worth reading and and worth following if you do not have good reasons not to. In you case, your function name for instance is not compliant to PEP8. You'll find tools online to check your code compliancy to PEP8 in a automated way if you want to.

Docstrings

There are Python docstring conventions you can find in PEP 257. Instead of

# Takes an integer, returns true or false
def isPrime(number):


You could write :

def isPrime(number):
"""Return whether an integer is prime."""


Please note: the imperative tone, the triple-quote strings under the def line, the ending period.

Do less

If your function isPrime takes an integer as a parameter, you do not need number = int(number).

Also, you can rewrite :

# Check if the only factors are 1 and itself and it is greater than 1
if len(findFactors(number)) == 2 and number > 1:
return True

return False


as

# Check if the only factors are 1 and itself and it is greater than 1
return len(findFactors(number)) == 2 and number > 1


Different algorithm

You do not really need to find the list of all factors to know if the number is prime. You can stop as soon as a factor is found.

Let's say you have a number, 18. You find the factors as follows:

1 Bingo 18
2 Bingo 9
3 Bingo 6
4 NOPE
5 NOPE
6 Bingo -^- OOPS, we already used that


We could have guaranteed that we already used it before even reaching that point. Why? Because the square root of 18 (rounded down) is 4. If a number higher than 4 is checked, we will already have gotten it before. We know that because if the number (6) is higher than the square root, the number that we multiply it by to get the original (3) must be lower than the square root. If it were higher, well a number higher than the square root times another number higher than the square root must result in a number higher than the original (18). Therefore, the other number must be lower. Since we already did all of the numbers lower, we already found this one when we found 3. Therefore, your findFactors function needs to go only as high as math.sqrt(num).

Your function names do not comply with PEP 8, the Python style guide. I would recommend that you read that style guide and maybe even install some program to check your code against it.

Why do you need to find a list of factors just to know whether or not the number is prime? If it has just one factor, we know it isn't prime. If you want to keep findFactors() anyway, maybe you should change it to using yield ... instead of factors.append(...) so that it is a generator. Anything else using it can still do list(findFactors(...)), but it is advantageous for this because your isPrime function can now do:

try:
next(findFactors(number))
return True
except StopIteration:
return False


and be considerably more efficient for higher numbers.

You never should use this pattern:

if ...:
return True
return False


because there is something you might not have noticed. Let's say ... is True, you return True. If not (it equals False), you return False. Notice how you are just returning whatever ... is? Therefore, you can simply do:

return ...


If ... might be a Truthy or Falsy value, but is not necessarily a boolean, just convert it:

return bool(...)


In the case of the last couple lines of isPrime(), you don't need the conversion:

return len(findFactors(number)) == 2 and number > 1