Largest Prime Number possible from a subsequence of a Binary String | C ++ Program to implement the above approach ; Function to check if a number is prime or not ; Return not prime ; If prime return true ; Function to find the largest prime number possible from a subsequence ; Stores pairs of subsequences and their respective decimal value ; Stores the answer ; Traverse the string ; Stores the size of the vector ; Traverse the vector ; Extract the current pair ; Get the binary string from the pair ; Stores equivalent decimal values ; If the current character is '1' ; Add the character to the subsequence ; Update the value by left shifting the current value and adding 1 to it ; If s [ i ] = = '0' ; Add the character to the subsequence ; Update the value by left shifting the current value and adding 0 to it ; Store the subsequence in the vector ; Check if the decimal representation of current subsequence is prime or not ; If prime ; Update the answer with the largest one ; If no prime number could be obtained ; Driver Code ; Input String
#include <iostream> NEW_LINE #include <vector> NEW_LINE using namespace std ; bool isPrime ( int x ) { if ( x <= 1 ) return false ; for ( int i = 2 ; i * i <= x ; i ++ ) { if ( x % i == 0 ) return false ; } return true ; } void largestPrime ( string s ) { vector < pair < string , int > > vec { { " " , 0 } } ; int ans = 0 ; for ( int i = 0 ; i < s . length ( ) ; i ++ ) { int n = vec . size ( ) ; for ( int j = 0 ; j < n ; j ++ ) { pair < string , int > temp = vec [ j ] ; string str = temp . first ; int val = temp . second ; if ( s [ i ] == '1' ) { temp . first = str + '1' ; temp . second = ( ( val << 1 ) + 1 ) ; } else { temp . first = str + '0' ; temp . second = ( ( val << 1 ) + 0 ) ; } vec . push_back ( temp ) ; int check = temp . second ; if ( isPrime ( check ) ) { ans = max ( ans , check ) ; } } } if ( ans == 0 ) cout << -1 << endl ; else cout << ans << endl ; } int main ( ) { string s = "110" ; largestPrime ( s ) ; return 0 ; }