Length of largest sub | Javascript 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
let prime = new Array ( 1000000 + 5 ) ; function findPrime ( ) { prime . fill ( true ) prime [ 1 ] = false ; for ( let p = 2 ; p * p <= 1000000 ; p ++ ) { if ( prime [ p ] == true ) { for ( let i = p * 2 ; i <= 1000000 ; i += p ) prime [ i ] = false ; } } } function lenOfLongSubarr ( arr , n ) { let um = new Map ( ) ; let sum = 0 , maxLen = 0 ; for ( let i = 0 ; i < n ; i ++ ) { sum += prime [ arr [ i ] ] == 0 ? - 1 : 1 ; if ( sum == 1 ) maxLen = i + 1 ; else if ( ! um . has ( sum ) ) um . set ( sum , i ) ; if ( um . has ( sum - 1 ) ) { if ( maxLen < ( i - um . get ( sum - 1 ) ) ) maxLen = i - um . get ( sum - 1 ) ; } } return maxLen ; } findPrime ( ) ; let arr = [ 1 , 9 , 3 , 4 , 5 , 6 , 7 , 8 ] ; let n = arr . length ; document . write ( lenOfLongSubarr ( arr , n ) + " " )