Length of largest sub | C ++ implementation of above approach ; If prime [ p ] is not changed , then it is a prime ; Update all multiples of p ; Function to find the length of longest subarray having count of primes more than count of non - primes ; unordered_map ' um ' implemented as hash table ; traverse the given array ; consider - 1 as non primes and 1 as primes ; when subarray starts form index '0' ; make an entry for ' sum ' if it is not present in ' um ' ; check if ' sum - 1' is present in ' um ' or not ; update maxLength ; required maximum length ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool prime [ 1000000 + 5 ] ; void findPrime ( ) { memset ( prime , true , sizeof ( prime ) ) ; prime [ 1 ] = false ; for ( int p = 2 ; p * p <= 1000000 ; p ++ ) { if ( prime [ p ] == true ) { for ( int i = p * 2 ; i <= 1000000 ; i += p ) prime [ i ] = false ; } } } int lenOfLongSubarr ( int arr [ ] , int n ) { unordered_map < int , int > um ; int sum = 0 , maxLen = 0 ; for ( int i = 0 ; i < n ; i ++ ) { sum += prime [ arr [ i ] ] == 0 ? -1 : 1 ; if ( sum == 1 ) maxLen = i + 1 ; else if ( um . find ( sum ) == um . end ( ) ) um [ sum ] = i ; if ( um . find ( sum - 1 ) != um . end ( ) ) { if ( maxLen < ( i - um [ sum - 1 ] ) ) maxLen = i - um [ sum - 1 ] ; } } return maxLen ; } int main ( ) { findPrime ( ) ; int arr [ ] = { 1 , 9 , 3 , 4 , 5 , 6 , 7 , 8 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << lenOfLongSubarr ( arr , n ) << endl ; return 0 ; }