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