Smallest prime number missing in an array | This function finds all prime numbers upto 10 ^ 5 ; use sieve to find prime ; If number is prime , then store it in prime list ; Function to find the smallest prime missing ; first of all find all prime ; now store all number as index of freq arr so that we can improve searching ; now check for each prime ; Driver Code ; find smallest prime which is not present
def findPrime ( MAX ) : NEW_LINE INDENT pm = [ True ] * ( MAX + 1 ) NEW_LINE pm [ 0 ] , pm [ 1 ] = False , False NEW_LINE for i in range ( 2 , MAX + 1 ) : NEW_LINE INDENT if pm [ i ] == True : NEW_LINE INDENT for j in range ( 2 * i , MAX + 1 , i ) : NEW_LINE INDENT pm [ j ] = False NEW_LINE DEDENT DEDENT DEDENT prime = [ ] NEW_LINE for i in range ( 0 , MAX + 1 ) : NEW_LINE INDENT if pm [ i ] == True : NEW_LINE INDENT prime . append ( i ) NEW_LINE DEDENT DEDENT return prime NEW_LINE DEDENT def findSmallest ( arr , n ) : NEW_LINE INDENT MAX = max ( arr ) NEW_LINE prime = findPrime ( MAX ) NEW_LINE s = set ( ) NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT s . add ( arr [ i ] ) NEW_LINE DEDENT ans = - 1 NEW_LINE for i in range ( 0 , len ( prime ) ) : NEW_LINE INDENT if prime [ i ] not in s : NEW_LINE INDENT ans = prime [ i ] NEW_LINE break NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 3 , 0 , 1 , 2 , 7 ] NEW_LINE n = len ( arr ) NEW_LINE if ( findSmallest ( arr , n ) == - 1 ) : NEW_LINE INDENT print ( " No ▁ prime ▁ number ▁ missing " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( findSmallest ( arr , n ) ) NEW_LINE DEDENT DEDENT