Count subarrays with Prime sum | Function to count subarrays with Prime sum ; USE SIEVE TO FIND ALL PRIME NUMBERS LESS THAN OR EQUAL TO max_val Create a boolean array " prime [ 0 . . n ] " . A value in prime [ i ] will finally be false if i is Not a prime , else true . ; Remaining part of SIEVE ; If prime [ p ] is not changed , then it is a prime ; Update all multiples of p ; Initialize result ; Traverse through the array ; return answer ; Driver Code
def primeSubarrays ( A , n ) : NEW_LINE INDENT max_val = 10 ** 7 NEW_LINE prime = [ True ] * ( max_val + 1 ) NEW_LINE prime [ 0 ] = False NEW_LINE prime [ 1 ] = False NEW_LINE for p in range ( 2 , int ( max_val ** ( 0.5 ) ) + 1 ) : NEW_LINE INDENT if prime [ p ] == True : NEW_LINE INDENT for i in range ( 2 * p , max_val + 1 , p ) : NEW_LINE INDENT prime [ i ] = False NEW_LINE DEDENT DEDENT DEDENT cnt = 0 NEW_LINE for i in range ( 0 , n - 1 ) : NEW_LINE INDENT val = A [ i ] NEW_LINE for j in range ( i + 1 , n ) : NEW_LINE INDENT val += A [ j ] NEW_LINE if prime [ val ] == True : NEW_LINE INDENT cnt += 1 NEW_LINE DEDENT DEDENT DEDENT return cnt NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT A = [ 1 , 2 , 3 , 4 , 5 ] NEW_LINE n = len ( A ) NEW_LINE print ( primeSubarrays ( A , n ) ) NEW_LINE DEDENT