Approach : Prefix Sum with Prime Check

#include <iostream>
#include <vector>
#include <cmath>

// Function to check if a number is prime
bool is_prime(int n) {
    if (n <= 1) {
        return false;  // Numbers less than or equal to 1 are not prime
    }
    for (int i = 2; i <= std::sqrt(n); ++i) {
        if (n % i == 0) {
            return false;  // Found a divisor, so n is not prime
        }
    }
    return true;  // No divisors found, so n is prime
}

// Function to count subarrays with prime sum
int count_prime_sum_subarrays(const std::vector<int>& A) {
    int n = A.size();
    std::vector<int> prefix(n + 1, 0);
    
    // Create prefix sum array
    // prefix[i] will store the sum of elements from A[0] to A[i-1]
    for (int i = 0; i < n; ++i) {
        prefix[i + 1] = prefix[i] + A[i];
    }
    
    int count = 0;
    // Check subarray sums using prefix array
    // Consider all subarrays with size > 1
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            // Calculate the sum of subarray A[i:j+1]
            int subarray_sum = prefix[j + 1] - prefix[i];
            // Check if this sum is prime
            if (is_prime(subarray_sum)) {
                count++;  // Increment count if the sum is prime
            }
        }
    }
    
    return count;
}

int main() {
    std::vector<int> A = {22, 33, 4, 1, 10};
    std::cout << count_prime_sum_subarrays(A) << std::endl; 
    return 0;
}

// This code is contributed by Shivam

// C++ program to count subarrays
// with Prime sum

#include <bits/stdc++.h>
using namespace std;

// Function to count subarrays
// with Prime sum
int primeSubarrays(int A[], int n)
{
    int max_val = int(pow(10, 7));

    // 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.
    vector<bool> prime(max_val + 1, true);

    // Remaining part of SIEVE
    prime[0] = false;
    prime[1] = false;
    for (int p = 2; p * p <= max_val; p++) {

        // If prime[p] is not changed, then
        // it is a prime
        if (prime[p] == true) {

            // Update all multiples of p
            for (int i = p * 2; i <= max_val; i += p)
                prime[i] = false;
        }
    }

    int cnt = 0; // Initialize result

    // Traverse through the array
    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 answer
    return cnt;
}

// Driver program
int main()
{
    int A[] = { 1, 2, 3, 4, 5 };
    int n = sizeof(A) / sizeof(A[0]);

    cout << primeSubarrays(A, n);

    return 0;
}