How to Check for a Prime Number Using Python and Determine the Big O Complexity

Table of Content

• What is a Prime Number?
• How to Determine if a Number is a Prime Number in Python
• Optimal Solution to Determine if a Number is a Prime Number in Python
• How to Determine the Big O Complexity of a Prime Number
• Wrap Off

In this lesson, we will go over writing a program in Python to determine if a number is a prime number and find the big O complexity.

What is a Prime Number?

A prime number is a natural number greater than 1 that is only divisible by itself and one.

Some characteristics of a prime number include:

• It is greater than 1
• It is a factor of itself and 1.

For example, the number 7 is a prime number since it can only be expressed as 1 into 7 or 7 into 1.

The number 4, on the other hand, is not a prime number, since it is divisible by 2.

Let's represent the above as a function and output:

prime_number(7) # true
prime_number(4) # false

How to Determine if a Number is a Prime Number in Python

Here is a typical problem statement to determine if a number is a prime number.

Given a natural number n, determine if the number is prime or not,

Alright, let's solve the problem together.

We will begin by defining the function named prime_number in Python.

The function will have one parameter n, which denotes the natural number to determine if it's prime or not.

For example, calling the function with n equal to 4 and 7 should return true and false respectively.

def prime_number(n):
	...

Next, what do we know about prime numbers?

Well, one characteristic is that it is a natural number greater than 1.

So, let's begin by adding an if condition to check if n is less than 2 to return false.

def prime_number(n):
	if n < 2:
    	return False

So, if we call the function and pass in 1, 0, or any negative number, it will return false.

Next, if n is greater than 1 we need to check if it is divisible by any smaller number.

For that, we will use a for loop that starts at 2, since every number is divisible by 1, and compare until we get to n.

To do this in python, we will use the modulus operation to get the remainder of a division.

If n modulus is any number other than itself and 1, then the function will return false, since it's not a prime number.

However, if the loop completes and no number could divide n, it is prime, and we return true.

def prime_number(n):
	if n < 2:
    	return False
    for i in range(2, n):
	    if n % i == 0:
		    return False
	return True

That is pretty much the code required to test if a number is a prime number.

Let's verify by running:

print(prime_number(4))
print(prime_number(7))

Optimal Solution to Determine if a Number is a Prime Number in Python

If you are good at math, you will probably know a slightly more optimal solution using the characteristics of a division.

When finding a prime number, the integers larger than the square root of that number do not need to be checked because, whenever n = a * b, one of the two factors, a or b, will be less than or equal to the square root of n.

This means that if a number is a composite, that is not prime, you will find a divisor at less than or equal to the square root of that number.

Here are two simple examples to validate the statement.

Take n = 24,
the square root of 24 is ±4.89,
the closest factors are a = 4 and b = 6.
4 < 4.89, therefore, a is less than the square root of n.

Take n = 35,
the square root of 24 is ±5.91,
the closest factors are a = 5 and b = 7.
5 < 5.91, therefore, a is less than the square root of n.

This implies that we can change the comparison in our for loop to reflect the square root.

from math import sqrt, ceil

def prime_number(n):
	if n < 2:
    	return False
    for i in range(2, ceil(sqrt(n)) + 1):
	    if sqrt(n) % i == 0:
		    return False
	return True

In the code above, we imported the square root and rounding function from python's math module.

Next, we modify the code to get the number greater or equal to the square root of n, and we added 1 to it because the range function might skip the loop if the result of ceil(sqrt(n)) is 2.

Let's verify by running:

print(prime_number(4))
print(prime_number(7))

How to Determine the Big O Complexity of a Prime Number

Next, we will determine the big O of the program for checking if a number is a prime number in Python.

To determine the big O complexity of the function, you can either determine how many times each step is executed and then approximate the big O, as we have learned before, or you can use the rule of thumb we gave in this section as a shortcut to speed up the process.

Let's determine the big O together.

For the first program, our function contains one for loop, which repeats n times.

It will take a linear complexity since the for loop runs from the starting point until the final n value.

This means if n is equal to 100, we check till n is equal to 100. If n is equal to 10,000, we check till 10,000.

So the time complexity = O(n)

For the second program, our function contains one for loop as well, but it does not repeat n times.

The solution is more optimal because we skip checking too many figures of n.

This means if n is equal to 100, we check till n is equal to 10. If n is equal to 10,000, we check till 100.

The time complexity is the square root of n.

So the time complexity = O(sqrt(n)) = O(n^1/2)

Wrap Off

There you have it!

If you learned from this tutorial, or it helped you in any way, please consider sharing and subscribing to our newsletter.

Please share this post and for more insightful posts on business, technology, engineering, history, and marketing, subscribe to our newsletter.