Smallest prime number missing in an array | C ++ implementation of the above approach ; this store all prime number upto 10 ^ 5 this function find all prime ; use sieve to find prime ; if number is prime then store it in prime vector ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ll  long long int NEW_LINE vector < ll > findPrime ( int MAX ) { bool pm [ MAX + 1 ] ; memset ( pm , true , sizeof ( pm ) ) ; pm [ 0 ] = pm [ 1 ] = false ; for ( int i = 2 ; i <= MAX ; i ++ ) if ( pm [ i ] ) for ( int j = 2 * i ; j <= MAX ; j += i ) pm [ j ] = false ; vector < ll > prime ; for ( int i = 0 ; i <= MAX ; i ++ ) if ( pm [ i ] ) prime . push_back ( i ) ; return prime ; } int findSmallest ( int arr [ ] , int n ) { int MAX = * max_element ( arr , arr + n ) ; vector < ll > prime = findPrime ( MAX ) ; unordered_set < int > s ; for ( int i = 0 ; i < n ; i ++ ) s . insert ( arr [ i ] ) ; int ans = -1 ; for ( int i = 0 ; i < prime . size ( ) ; i ++ ) if ( s . find ( prime [ i ] ) == s . end ( ) ) { ans = prime [ i ] ; break ; } return ans ; } int main ( ) { int arr [ ] = { 3 , 0 , 1 , 2 , 7 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; if ( findSmallest ( arr , n ) == -1 ) cout << " No ▁ prime ▁ number ▁ missing " ; else cout << findSmallest ( arr , n ) ; return 0 ; }