Prime Numbers in Python
Definition of a Prime Number
Please read the first two paragraphs of this article on Wikipedia to get an understanding of prime numbers.
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
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.
Please note that the following code snippets were written for Python 3.
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 )