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
< ? php function primeCount ( $ arr , $ n ) { $ max_val = max ( $ arr ) ; $ prime = array_fill ( 0 , $ max_val + 1 , true ) ; $ prime [ 0 ] = false ; $ prime [ 1 ] = false ; for ( $ p = 2 ; $ p * $ p <= $ max_val ; $ p ++ ) { if ( $ prime [ $ p ] == true ) { for ( $ i = $ p * 2 ; $ i <= $ max_val ; $ i += $ p ) $ prime [ $ i ] = false ; } } $ count = 0 ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) if ( $ prime [ $ arr [ $ i ] ] ) $ count ++ ; return $ count ; } function getPrefixArray ( $ arr , $ n , $ pre ) { $ pre [ 0 ] = $ arr [ 0 ] ; for ( $ i = 1 ; $ i < $ n ; $ i ++ ) { $ pre [ $ i ] = $ pre [ $ i - 1 ] + $ arr [ $ i ] ; } return $ pre ; } $ arr = array ( 1 , 4 , 8 , 4 ) ; $ n = count ( $ arr ) ; $ pre = array ( ) ; $ pre = getPrefixArray ( $ arr , $ n , $ pre ) ; echo primeCount ( $ pre , $ n ) ; ? >