Length of longest subarray having only K distinct Prime Numbers | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool isprime [ 2000010 ] ; void SieveOfEratosthenes ( int n ) { memset ( isprime , true , sizeof ( isprime ) ) ; 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 ; } } } int KDistinctPrime ( int arr [ ] , int n , int k ) { SieveOfEratosthenes ( 2000000 ) ; map < int , int > cnt ; int result = -1 ; for ( int i = 0 , j = -1 ; i < n ; ++ i ) { int x = arr [ i ] ; if ( isprime [ x ] ) { if ( ++ cnt [ x ] == 1 ) { -- k ; } } while ( k < 0 ) { x = arr [ ++ j ] ; if ( isprime [ x ] ) { if ( -- cnt [ x ] == 0 ) { ++ k ; } } } if ( k == 0 ) result = max ( result , i - j ) ; } return result ; } int main ( void ) { int arr [ ] = { 1 , 2 , 3 , 3 , 4 , 5 , 6 , 7 , 8 , 9 } ; int K = 3 ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << KDistinctPrime ( arr , N , K ) ; return 0 ; }