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 program
< ? php function primeSubarrays ( $ A , $ n ) { $ max_val = pow ( 10 , 5 ) ; $ 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 ; } } $ cnt = 0 ; for ( $ i = 0 ; $ i < $ n - 1 ; ++ $ i ) { $ val = $ A [ $ i ] ; for ( $ j = $ i + 1 ; $ j < $ n ; ++ $ j ) { $ val += $ A [ $ j ] ; if ( $ prime [ $ val ] ) ++ $ cnt ; } } return $ cnt ; } $ A = array ( 1 , 2 , 3 , 4 , 5 ) ; $ n = count ( $ A ) ; echo primeSubarrays ( $ A , $ n ) ; ? >