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
Leave a Reply