Skip to content

Instantly share code, notes, and snippets.

@AmaxJ
Created January 15, 2015 22:33
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save AmaxJ/5719a927dbfa937d2a51 to your computer and use it in GitHub Desktop.
Save AmaxJ/5719a927dbfa937d2a51 to your computer and use it in GitHub Desktop.
primechecker
def isPrime(num):
prime = True
for x in range(2, num):
if num % x == 0:
prime = False
return prime
@davidwitten
Copy link

You don't have to check from 2 to the number, just to the square root. Here's an example: 100, whose square root is 10. Whenever you have a factor, like 5, 100/5 will be on the other side of the square root, so you only have to go up until the square root to determine if it's prime.

Also, you should exit out of the loop once you've determined that it's composite, so instead of setting prime to False, return False right away, and return True at the end.

Also, once you check two, you shouldn't check four or six, as they are multiples of two, so just check for 2, then 3, then 5 ... to the square root. That halves the operations necessary to determine if a number is prime.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment