Prime Numbers in Python

From Of The Nerds

Definition of a Prime Number

Please read the first two paragraphs of this article on Wikipedia to get an understanding of prime numbers.

Why Python?

Python is a good option for mathematical things like determining if a number is prime or not for two main reasons:

  • Python has a very simple syntax which is easy to understand
  • Python has no upper limit on how big integers can be

Algorithm

We'll be using trial division as it is one of the simplest algorithms to implement, is fast enough for most use cases, and has a 100% accuracy rating. Trial division simply tests if there's a factor between 2 and the square root of the number in question.

Python Implementation

Please note that the following code snippets were written for Python 3.

Code

1 import math
2 def is_prime( n ):
3   if n < 1:
4     return False
5   for i in range( 2, int( math.sqrt( n ) ) ):
6     if n % i == 0:
7       return False
8   return True

Step by step

First, we'll need to import the math library (to get the square root of numbers), and begin to define our function:

import math
def is_prime( n ):

Now let's check if the number is greater than 1 and return False if it isn't because prime numbers must be larger than 1:

if n < 1:
  return False

Next, let's use a for loop to go through all numbers between 2 and the square root of the number, and converting the square root to an integer:

for i in range( 2, int( math.sqrt( n ) ) ):

Lastly, we simply check if the number is evenly divisible (by checking if the % operator returns a zero) with the current number in the loop. If it is, we can safely return False as we now have a factor. If we make it to the end of the loop without exiting (return statement automatically end the function):

if n % i == 0:
  return False
# Outside of the loop
return True

Please see the full code to get the correct indentation levels.

Using the function

Now that we have our function, let's build a simple program to check if a number is prime or not. First, copy and paste the full function into your program. Now, let's just get the user input and return what the function gives us:

num = int( input( "Number: " ) )
if is_prime( num ):
  print( "%i is prime" %num )
else:
  print( "%i is NOT prime" % num )