How to check if a number is prime in python?

Prime Number is a natural number greater than 1, which is divisible by 1 and itself. For example, 2, 5, 3, 7 are all prime numbers. A composite number is a number greater than 1, that is divisible by a number other than 1 and itself. This article discusses several approaches to check if a number is prime or not.

Let us consider the example given below. A variable num is declared which takes input from the user. Another variable flag is initialized to 0. Numbers less than or equal to 1 are not prime numbers. The if statement checks if the number is greater than 1. If the condition is True the control of the program executes the for loop.

The for loop iterates for a range of 2 to num-1. In each iteration, the program checks if the number num is divisible by any number in that range. If a factor is found in that range number is not prime and the variable flag is set to 1. Otherwise, if the value of the variable flag remains 0, this indicates a number num is a prime number.

The time Complexity for the below program is O(N).

num = int(input("Enter a number: "))
flag = 0
if num > 1:
    for i in range(2, num):
        if num % i == 0:
            flag = 1
            print(num, " is not a Prime Number")
            break
    if flag == 0:
        print(num, "is a Prime Number")
else:
    print(num, " is not a Prime Number")

The above program is checked for multiple test cases, which returns the output as

Enter a number:  7
7 is a Prime Number

Enter a number:  14
14  is not a Prime Number

Enter a number:  -9
-9  is not a Prime Number​

Checking if a number is prime using for and while loop (Time Complexity O(sqrt(N)) )

We know that every composite number has at least one prime factor less than or equal to the square root of the number itself. So, instead of checking till the number(num), we can check till (sqrt(num)). This reduces the time complexity to O( sqrt(num)).

import math
num = int(input("Enter a number: "))
flag = 0
if num > 1:
    for i in range(2, int(math.sqrt(num))+ 1):
        if num % i == 0:
            flag = 1
            print(num, " is not a Prime Number")
            break
    if flag == 0:
        print(num, "is a Prime Number")
else:
    print(num, " is not a Prime Number")

Output

Enter a number: 7
7 is a Prime Number

This algorithm can be improved further. All the prime numbers except 2 and 3 are of the form 6k ± 1 where k is a positive integer greater than 0. So first, we will check if the number is divisible by 2 or 3 or the number is less than or equal to 1. If the condition is True number is not a Prime number.

Otherwise, we will check if the number is divisible by any of the prime numbers less than sqrt(num). If the condition is True number is not prime else a number is a Prime number.

import math
num = int(input("Enter a number: "))
if (num%2 == 0) or (num%3 == 0) or (num <= 1):
    print(num, "is not a Prime Number")
else:
    flag = 0
    i = 5 # initializing i to 6k-1, where k =1
    while( i <= int(math.sqrt(num))):
        # checking if num is divisible by 6k ± 1
        if (num % i == 0) or (num % (i+2) == 0): 
            flag = 1
            print(num, " is not a Prime Number")
            break
        i = i + 6 # incrementing i in each time by 6 steps 
    if flag == 0:
        print(num, "is a Prime Number")

The above code is check for multiple test cases given below which returns the output as

Enter a number: 9
9 is not a Prime Number

Enter a number:  7
7 is a Prime Number

Enter a number: -43
-43 is not a Prime Number

Finding all the prime numbers less than or equal to N using for loop (Time Complexity O(N2))

Let us consider an example, where we find all the prime numbers till N = 15 . We initialize an empty list list_prime to store all the prime numbers. A for loop iterates over the range of 2 and 15. In each iteration it checks if the number is prime by using another nested for loop.

If the number is not prime, the break statement breaks the loop. Otherwise, the else block appends the number to list_prime.

N = 15
list_prime = []
for num in range(2, N+1):
    if num > 1:
        for i in range(2, num):
           if num % i == 0:
              break
        else:
            list_prime.append(num)
print("list_prime: ", list_prime)

Output

list_prime:  [2, 3, 5, 7, 11, 13]

Find all the prime numbers less than or equal to N using Sieve of Eratosthenes (Time Complexity O(N log log(N))

Sieve of Eratosthenes is the most efficient algorithm to generate all the prime numbers for a given range. Let us consider a number n, We have to find all the prime numbers from 2 to n.

Algorithm :
  1. Create a list from 2 to n with the value True. The algorithm starts with the smallest prime number 2. The variable p is initialized to 2, p = 2.
  2. Mark all the multiples of p from 2p, 3p, 4p....... n as False(This indicates all the numbers marked with False are not prime).
  3. The program then finds the smallest unmarked number greater than p and initializes the variable p with that number.
  4. If there is no such number, then the process stops. Otherwise, it repeats the execution from step 2.

It is sufficient to mark the numbers in step 2 starting from p2 (p*p), as all the smaller multiples of p will have already been marked at that point.

Consider the following example, a variable n is initialized to value 15. The list_1 of length (n +1) is created and is initialized with True. The variable p in initialized to 2. The while loop checks if p is prime(if list_1[p] is not change to Flase, then p is prime) and marks all the multiples of p to value False. The value of p is incremented by 1 in each iteration.

Another for loop traverses the list_1 from 2 to n+1. If the value at that index is True, The index number is appended to list list_prime.

n =15    
list_1 = [True for i in range(n+1)]
p = 2
while (p * p <= n):
    # If list_1[p] is not changed to False,
    # then it is a prime
    if (list_1[p] == True):
        # All the multiples of p are updated
        for i in range(p * p, n+1, p):
            list_1[i] = False
    p += 1
list_prime =[]
for p in range(2, n+1):
    if list_1[p] == True:
        list_prime.append(p)
print("list_prime: ", list_prime)

The above code returns the output as

list_prime:  [2, 3, 5, 7, 11, 13]
0 results
Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions