Count the number of primes in the prefix sum array of the given array | Function to return the count of primes in the given array ; Find maximum value in the array ; 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 ; Find all primes in arr [ ] ; Function to generate the prefix array ; Fill the prefix array ; Driver code ; Prefix array of arr [ ] ; Count of primes in the prefix array
def primeCount ( arr , n ) : NEW_LINE INDENT max_val = max ( arr ) NEW_LINE prime = [ True ] * ( max_val + 1 ) NEW_LINE prime [ 0 ] = prime [ 1 ] = False NEW_LINE p = 2 NEW_LINE while p * p <= max_val : NEW_LINE INDENT if prime [ p ] == True : NEW_LINE INDENT for i in range ( p * 2 , max_val + 1 , p ) : NEW_LINE INDENT prime [ i ] = False NEW_LINE DEDENT DEDENT p += 1 NEW_LINE DEDENT count = 0 NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT if prime [ arr [ i ] ] : NEW_LINE INDENT count += 1 NEW_LINE DEDENT DEDENT return count NEW_LINE DEDENT def getPrefixArray ( arr , n , pre ) : NEW_LINE INDENT pre [ 0 ] = arr [ 0 ] NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT pre [ i ] = pre [ i - 1 ] + arr [ i ] NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , 4 , 8 , 4 ] NEW_LINE n = len ( arr ) NEW_LINE pre = [ None ] * n NEW_LINE getPrefixArray ( arr , n , pre ) NEW_LINE print ( primeCount ( pre , n ) ) NEW_LINE DEDENT