Count of subarrays having exactly K prime numbers | Python3 program for the above approach ; A utility function to check if the number n is prime or not ; Base Cases ; Check to skip middle five numbers in below loop ; If n is divisible by i & i + 2 then it is not prime ; Function to find number of subarrays with sum exactly equal to k ; STL map to store number of subarrays starting from index zero having particular value of sum . ; To store the sum of element traverse so far ; Add current element to currsum ; If currsum = K , then a new subarray is found ; If currsum > K then find the no . of subarrays with sum currsum - K and exclude those subarrays ; Add currsum to count of different values of sum ; Return the final result ; Function to count the subarray with K primes ; Update the array element ; If current element is prime then update the arr [ i ] to 1 ; Else change arr [ i ] to 0 ; Function Call ; Driver Code ; Function Call
from math import sqrt NEW_LINE def isPrime ( n ) : NEW_LINE INDENT if ( n <= 1 ) : NEW_LINE INDENT return False NEW_LINE DEDENT if ( n <= 3 ) : NEW_LINE INDENT return True NEW_LINE DEDENT if ( n % 2 == 0 or n % 3 == 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT for i in range ( 5 , int ( sqrt ( n ) ) + 1 , 6 ) : NEW_LINE INDENT if ( n % i == 0 or n % ( i + 2 ) == 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT return True NEW_LINE DEDENT def findSubarraySum ( arr , n , K ) : NEW_LINE INDENT prevSum = { i : 0 for i in range ( 100 ) } NEW_LINE res = 0 NEW_LINE currsum = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT currsum += arr [ i ] NEW_LINE if ( currsum == K ) : NEW_LINE INDENT res += 1 NEW_LINE DEDENT if ( currsum - K ) in prevSum : NEW_LINE INDENT res += ( prevSum [ currsum - K ] ) NEW_LINE DEDENT prevSum [ currsum ] += 1 NEW_LINE DEDENT return res NEW_LINE DEDENT def countSubarray ( arr , n , K ) : NEW_LINE INDENT for i in range ( n ) : NEW_LINE INDENT if ( isPrime ( arr [ i ] ) ) : NEW_LINE INDENT arr [ i ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT arr [ i ] = 0 NEW_LINE DEDENT DEDENT print ( findSubarraySum ( arr , n , K ) ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 2 , 3 , 4 ] NEW_LINE K = 2 NEW_LINE N = len ( arr ) NEW_LINE countSubarray ( arr , N , K ) NEW_LINE DEDENT