Python Program to find smallest missing prime number in an array

Given an array containing n distinct numbers. We will learn how to find the smallest missing prime number in the given array in Python.

Example

Input: arr[] = {2, 3, 9, 10, 5, 6}
Output: 7
7 is a prime number. Which is not prime in array.

Input: arr[] = {0, 3, 5, 1, 7}
Output: No prime number is missing
7 is the maximum number. All the prime less than 7 are present in the array.

A number is said to be a prime number if it has only one and itself as roots.

Smallest missing prime number

1. Firstly, use the Sieve of Eratosthenes to find all the prime that is less than the maximum value of the given.

2. Iterate over the array and check whether the current number is present or not in prime.

3. Finally, return the missing prime number.

Below is our Python code that will be able to find the smallest missing prime number in our array:

def find_Prime(m): 

  prime_list = [True] * (m + 1) 

  prime_list[0], prime_list[1] = False, False
  
  for i in range(2, m + 1): 
    if prime_list[i] == True: 
      
      for j in range(2 * i, m + 1, i): 
        prime_list[j] = False

  prime = [] 
  for i in range(0, m + 1): 
    if prime_list[i] == True: 
      prime.append(i) 

  return prime 

def findSmallest(arr, n): 

  m = max(arr) 
  prime = find_Prime(m) 
  s = set() 
  for i in range(0, n): 
    s.add(arr[i]) 

  result = -1
  for i in range(0, len(prime)): 
    if prime[i] not in s: 
      result = prime[i] 
      break
    
  return result 


arr = [3, 0, 1, 2, 7] 
n = len(arr) 
if(findSmallest(arr, n) == -1): 
  print("No prime number missing") 
else: 
  print(findSmallest(arr, n)) 

Output

The smallest missing prime number is 11

Also, refer

• Circular Prime in Python