Length of longest subarray having only K distinct Prime Numbers | Python3 program to implement 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
from collections import defaultdict NEW_LINE isprime = [ True ] * 2000010 NEW_LINE def SieveOfEratosthenes ( n ) : NEW_LINE INDENT isprime [ 1 ] = False NEW_LINE p = 2 NEW_LINE while ( p * p <= n ) : NEW_LINE INDENT if ( isprime [ p ] == True ) : NEW_LINE INDENT for i in range ( p * p , n + 1 , p ) : NEW_LINE INDENT isprime [ i ] = False NEW_LINE DEDENT DEDENT p += 1 NEW_LINE DEDENT DEDENT def KDistinctPrime ( arr , n , k ) : NEW_LINE INDENT SieveOfEratosthenes ( 2000000 ) NEW_LINE cnt = defaultdict ( lambda : 0 ) NEW_LINE result = - 1 NEW_LINE j = - 1 NEW_LINE for i in range ( n ) : NEW_LINE INDENT x = arr [ i ] NEW_LINE if ( isprime [ x ] ) : NEW_LINE INDENT cnt [ x ] += 1 NEW_LINE if ( cnt [ x ] == 1 ) : NEW_LINE INDENT k -= 1 NEW_LINE DEDENT DEDENT DEDENT while ( k < 0 ) : NEW_LINE INDENT j += 1 NEW_LINE x = arr [ j ] NEW_LINE if ( isprime [ x ] ) : NEW_LINE INDENT cnt [ x ] -= 1 NEW_LINE if ( cnt [ x ] == 0 ) : NEW_LINE INDENT k += 1 NEW_LINE DEDENT DEDENT if ( k == 0 ) : NEW_LINE INDENT result = max ( result , i - j ) NEW_LINE DEDENT DEDENT return result NEW_LINE DEDENT arr = [ 1 , 2 , 3 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ] NEW_LINE K = 3 NEW_LINE N = len ( arr ) NEW_LINE print ( KDistinctPrime ( arr , N , K ) ) NEW_LINE