human
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"
Solution in Python:
 ... Write me a code to count the number of primes in the prefix sum array of the given array and the other steps required?
assistant
#Here is code to count the number of primes in the prefix sum array of the given array and the other steps required.
 def primeCount ( arr , n ) :
	max_val = max ( arr )
	prime = [ True ] * ( max_val + 1 )
	prime [ 0 ] = prime [ 1 ] = False
	p = 2
	while p * p <= max_val :
		if prime [ p ] == True :
			for i in range ( p * 2 , max_val + 1 , p ) :
				prime [ i ] = False
		p += 1
	count = 0
	for i in range ( 0 , n ) :
		if prime [ arr [ i ] ] :
			count += 1
	return count
def getPrefixArray ( arr , n , pre ) :
	pre [ 0 ] = arr [ 0 ]
	for i in range ( 1 , n ) :
		pre [ i ] = pre [ i - 1 ] + arr [ i ]
if __name__ == " _ _ main _ _ " :
	arr = [ 1 , 4 , 8 , 4 ]
	n = len ( arr )
	pre = [ None ] * n
	getPrefixArray ( arr , n , pre )
	print ( primeCount ( pre , n ) )