Length of longest subarray having only K distinct Prime Numbers | Java 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 ; Driver Code ; Given array arr [ ] ; Function call
import java . util . * ; import java . lang . * ; class GFG { static boolean [ ] isprime = new boolean [ 2000010 ] ; static void SieveOfEratosthenes ( int n ) { Arrays . fill ( isprime , true ) ; isprime [ 1 ] = false ; for ( int p = 2 ; p * p <= n ; p ++ ) { if ( isprime [ p ] == true ) { for ( int i = p * p ; i <= n ; i += p ) isprime [ i ] = false ; } } } static int KDistinctPrime ( int arr [ ] , int n , int k ) { SieveOfEratosthenes ( 2000000 ) ; Map < Integer , Integer > cnt = new HashMap < > ( ) ; int result = - 1 ; for ( int i = 0 , j = - 1 ; i < n ; ++ i ) { int x = arr [ i ] ; if ( isprime [ x ] ) { cnt . put ( x , cnt . getOrDefault ( x , 0 ) + 1 ) ; if ( cnt . get ( x ) == 1 ) { -- k ; } } while ( k < 0 ) { x = arr [ ++ j ] ; if ( isprime [ x ] ) { cnt . put ( x , cnt . getOrDefault ( x , 0 ) - 1 ) ; if ( cnt . get ( x ) == 0 ) { ++ k ; } } } if ( k == 0 ) result = Math . max ( result , i - j ) ; } return result ; } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 2 , 3 , 3 , 4 , 5 , 6 , 7 , 8 , 9 } ; int K = 3 ; int N = arr . length ; System . out . println ( KDistinctPrime ( arr , N , K ) ) ; } }