Check For Prime Number in Python

Prime numbers are those numbers that have only two factors i.e. 1 and the number itself. In this article, we will discuss two ways to check for a prime number in python.

What is a prime number?

Prime numbers are those positive integers greater than one that has only two factors. The examples of prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, etc.

Here, 

• 2 has only two factors i.e. 1 and 2.
• 3 has only two factors i.e. 1 and 3.
• 5 has only two factors i.e. 1 and 5.

You can observe that all other numbers also have only two factors. 

Check For Prime Number in Python

For checking if a number is prime or not, we just have to make sure that all the numbers greater than 1 and less than the number itself should not be a factor of the number. For this, we will define a function isPrime() that takes a number N as input. Then it checks whether any number between 2 and N-1 is a factor of N or not using a for loop. If a factor is present, it returns False stating that the input number N is not a prime number. Otherwise, it returns True.

def isPrime(N):
    for number in range(2, N):
        if N % number == 0:
            return False
    return True


input_number = 23
output = isPrime(input_number)
print("{} is a Prime number:{}".format(input_number, output))
input_number = 126
output = isPrime(input_number)
print("{} is a Prime number:{}".format(input_number, output))

Output:

23 is a Prime number:True
126 is a Prime number:False

In the above example, we have checked every number from 2 to N-1 to see if it is a factor of N or not. We can optimize this process by checking numbers till N/2 instead of N-1. This is so because the only factor of N greater than N/2 is the number N itself. So, we will check for factors in numbers only till N/2. Additionally, we can also check if a number is even or not. If a number greater than 2 is even, it will never be a prime number. We can define an improved isPrime() function using these concepts as given below.

def isPrime(N):
    for number in range(2, N//2):
        if N % number == 0:
            return False
    return True


input_number = 23
output = isPrime(input_number)
print("{} is a Prime number:{}".format(input_number, output))
input_number = 126
output = isPrime(input_number)
print("{} is a Prime number:{}".format(input_number, output))

Output:

23 is a Prime number:True
126 is a Prime number:False

We can again optimize the above program using simple logic. You can observe that factors of a number always occur in pairs. For a number N, the factors can be paired as (1, N), (2, N/2), (3, N/3), (4, N/4) till (N1/2, N^1/2). So, for checking for factors, we can check only till N^1/2 instead of N/2. 

For example, if we are given a number 100, all the factors can be paired as (1,100), (2,50),(4,25), (5,20), and (10,10). Here, if 100 is divisible by 2, it must be divisible by 50, if 100 is divisible by 4, it must be divisible by 25. We don’t need to explicitly check both the numbers in a pair to check if a number is a factor or not. So, To check for prime number, We can simply check for a factor till N^1/2 instead of N/2 using a while loop. If a factor is not present between 2 and N^1/2, the number must be a prime number. Using this logic, we can modify the isPrime() function used in the above example as follows.

def isPrime(N):
    count = 2
    while count ** 2 <= N:
        if N % count == 0:
            return False
        count = count + 1
    return True


input_number = 23
output = isPrime(input_number)
print("{} is a Prime number:{}".format(input_number, output))
input_number = 126
output = isPrime(input_number)
print("{} is a Prime number:{}".format(input_number, output))

Output:

23 is a Prime number:True
126 is a Prime number:False

Conclusion

In this article, we have discussed three ways to check for a prime number in python. To learn more about numbers, you can read this article on complex numbers in python. You might also like this article on decimal numbers in Python.