Count subarrays with Prime sum | C ++ program to 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int primeSubarrays ( int A [ ] , int n ) { int max_val = int ( pow ( 10 , 7 ) ) ; vector < bool > prime ( max_val + 1 , true ) ; prime [ 0 ] = false ; prime [ 1 ] = false ; for ( int p = 2 ; p * p <= max_val ; p ++ ) { if ( prime [ p ] == true ) { for ( int i = p * 2 ; i <= max_val ; i += p ) prime [ i ] = false ; } } int cnt = 0 ; for ( int i = 0 ; i < n - 1 ; ++ i ) { int val = A [ i ] ; for ( int j = i + 1 ; j < n ; ++ j ) { val += A [ j ] ; if ( prime [ val ] ) ++ cnt ; } } return cnt ; } int main ( ) { int A [ ] = { 1 , 2 , 3 , 4 , 5 } ; int n = sizeof ( A ) / sizeof ( A [ 0 ] ) ; cout << primeSubarrays ( A , n ) ; return 0 ; }