Length of longest subarray having only K distinct Prime Numbers | Javascript program for the above approach ; Function to precalculate all the prime up to 10 ^ 6 ; Initialize prime to true ; Iterate [ 2 , sqrt ( N ) ] ; If p is prime ; Mark all multiple of p as true ; Function that finds the length of longest subarray K distinct primes ; Precompute all prime up to 2 * 10 ^ 6 ; Keep track occurrence of prime ; Initialize result to - 1 ; If number is prime then increment its count and decrease k ; Decrement K ; Remove required elements till k become non - negative ; Decrease count so that it may appear in another subarray appearing after this present subarray ; Increment K ; Take the max value as length of subarray ; Return the final length ; Given array arr [ ] ; Function call
let isprime = new Array ( 2000010 ) ; function SieveOfEratosthenes ( n ) { isprime . fill ( true ) ; isprime [ 1 ] = false ; for ( let p = 2 ; p * p <= n ; p ++ ) { if ( isprime [ p ] == true ) { for ( let i = p * p ; i <= n ; i += p ) isprime [ i ] = false ; } } } function KDistinctPrime ( arr , n , k ) { SieveOfEratosthenes ( 2000000 ) ; let cnt = new Map ( ) ; let result = - 1 ; for ( let i = 0 , j = - 1 ; i < n ; ++ i ) { let x = arr [ i ] ; if ( isprime [ x ] ) { if ( cnt . has ( x ) ) cnt . set ( x , cnt . get ( x ) + 1 ) else cnt . set ( x , 1 ) ; if ( cnt . get ( x ) == 1 ) { -- k ; } } while ( k < 0 ) { x = arr [ ++ j ] ; if ( isprime [ x ] ) { if ( cnt . has ( x ) ) cnt . set ( x , cnt . get ( x ) - 1 ) else cnt . set ( x , - 1 ) ; if ( cnt . get ( x ) == 0 ) { ++ k ; } } } if ( k == 0 ) result = Math . max ( result , i - j ) ; } return result ; } let arr = [ 1 , 2 , 3 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ] ; let K = 3 ; let N = arr . length ; document . write ( KDistinctPrime ( arr , N , K ) ) ;