Subarray of size K with prime sum | Generate all prime numbers in the range [ 1 , 1000000 ] ; Set all numbers as prime initially ; Mark 0 and 1 as non - prime ; If current element is prime ; Mark all its multiples as non - prime ; Function to prthe subarray whose sum of elements is prime ; Store the current subarray of size K ; Calculate the sum of first K elements ; Check if currSum is prime ; Store the start and last index of subarray of size K ; Iterate over remaining array ; Check if currSum ; Driver Code
def sieve ( prime ) : NEW_LINE INDENT for i in range ( 1000000 ) : NEW_LINE INDENT prime [ i ] = True NEW_LINE DEDENT prime [ 0 ] = prime [ 1 ] = False NEW_LINE for i in range ( 2 , 1000 + 1 ) : NEW_LINE INDENT if ( prime [ i ] ) : NEW_LINE INDENT for j in range ( i * i , 1000000 , i ) : NEW_LINE INDENT prime [ j ] = False NEW_LINE DEDENT DEDENT DEDENT return prime NEW_LINE DEDENT def subPrimeSum ( N , K , arr , prime ) : NEW_LINE INDENT currSum = 0 NEW_LINE for i in range ( 0 , K ) : NEW_LINE INDENT currSum += arr [ i ] NEW_LINE DEDENT if ( prime [ currSum ] ) : NEW_LINE INDENT for i in range ( K ) : NEW_LINE INDENT print ( arr [ i ] , end = " ▁ " ) NEW_LINE DEDENT return NEW_LINE DEDENT st = 1 NEW_LINE en = K NEW_LINE while ( en < N ) : NEW_LINE INDENT currSum += arr [ en ] - arr [ st - 1 ] NEW_LINE if ( prime [ currSum ] ) : NEW_LINE INDENT for i in range ( st , en + 1 ) : NEW_LINE INDENT print ( arr [ i ] , end = " ▁ " ) NEW_LINE DEDENT return NEW_LINE DEDENT en += 1 NEW_LINE st += 1 NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 20 , 7 , 5 , 4 , 3 , 11 , 99 , 87 , 23 , 45 ] NEW_LINE K = 4 NEW_LINE N = len ( arr ) NEW_LINE prime = [ False ] * 1000000 NEW_LINE prime = sieve ( prime ) NEW_LINE subPrimeSum ( N , K , arr , prime ) NEW_LINE DEDENT