# Prime Numbers in Python

## 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 )