# Prime Numbers in Python

## Contents

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