Count subarrays with Prime sum

0 0 6 minutes read

Given an array A[] of integers. The task is to count total subarrays whose sum is prime with ( size > 1 ).

Examples:

Input : A[] = { 1, 2, 3, 4, 5 }
Output : 3
Subarrays are -> {1, 2}, {2, 3}, {3, 4}

Input : A = { 22, 33, 4, 1, 10 };
Output : 4

Approach: Generate all possible subarrays and store their sum in a vector. Iterate the vector and check whether a sum is prime or not. It YES increments the count.

You can use sieve-of-eratosthenes to check whether a sum is prime in O(1).

Below is the implementation of the above approach:

C++

// 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;
}

Java

// Java program to count subarrays 
// with Prime sum 
class GFG 
{
   
    // Function to count subarrays 
    // with Prime sum 
    static int primeSubarrays(int[] A, int n) 
    { 
        int max_val = 10000000;
     
        // 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. 
        boolean[] prime = new boolean[max_val + 1]; 
     
         
        //initialize initial value
        for (int p = 0; p < max_val + 1; p++)
        prime[p]=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 code
    public static void main(String[] args) {
        int[] A = { 1, 2, 3, 4, 5 }; 
        int n = A.length; 
     
        System.out.println(primeSubarrays(A, n)); 
    }
}
 
 
//This code is contributed by phasing17

Python3

# Python3 program to count subarrays 
# with Prime sum 
 
# Function to count subarrays 
# with Prime sum 
def primeSubarrays(A, n):
 
    max_val = 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. 
    prime = [True] * (max_val + 1) 
 
    # Remaining part of SIEVE 
    prime[0] = False
    prime[1] = False
    for p in range(2, int(max_val**(0.5)) + 1): 
 
        # If prime[p] is not changed, then 
        # it is a prime 
        if prime[p] == True: 
 
            # Update all multiples of p 
            for i in range(2 * p, max_val + 1, p):
                prime[i] = False
         
    cnt = 0 # Initialize result 
 
    # Traverse through the array 
    for i in range(0, n - 1): 
        val = A[i] 
        for j in range(i + 1, n): 
            val += A[j] 
 
            if prime[val] == True: 
                cnt += 1
 
    # return answer 
    return cnt 
 
# Driver Code
if __name__ == "__main__":
 
    A = [1, 2, 3, 4, 5] 
    n = len(A) 
 
    print(primeSubarrays(A, n))
 
# This code is contributed by Rituraj Jain

C#

// C# program to count subarrays 
// with Prime sum 
 
class Solution
{
 
// Function to count subarrays 
// with Prime sum 
static int primeSubarrays(int[] A, int n) 
{ 
    int max_val = (int)(System.Math.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. 
    bool[] prime=new bool[max_val + 1]; 
 
     
    //initialize initial value
    for (int p = 0; p <max_val + 1; p++)
    prime[p]=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 
static void Main()
{ 
    int[] A = { 1, 2, 3, 4, 5 }; 
    int n = A.Length; 
 
    System.Console.WriteLine( primeSubarrays(A, n)); 
 
} 
}
//contributed by mits

PHP

<?php
// PHP program to count subarrays 
// with Prime sum 
 
 
// Function to count subarrays 
// with Prime sum 
function primeSubarrays($A, $n) 
{ 
    $max_val = pow(10, 5); 
 
    // 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. 
    $prime=array_fill(0,$max_val + 1,true); 
 
    // Remaining part of SIEVE 
    $prime[0] = false; 
    $prime[1] = false; 
    for ($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 ($i = $p * 2; $i <= $max_val; $i += $p) 
                $prime[$i] = false; 
        } 
    } 
 
    $cnt = 0; // Initialize result 
 
    // Traverse through the array 
    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 answer 
    return $cnt; 
} 
 
// Driver program 
  
    $A = array( 1, 2, 3, 4, 5 ); 
    $n = count($A); 
 
    echo primeSubarrays($A, $n); 
 
// This code is contributed by mits 
?>

Javascript

<script>
 
// JavaScript program to count subarrays
// with Prime sum
 
 
// Function to count subarrays
// with Prime sum
function primeSubarrays(A, n)
{
    var max_val = parseInt(Math.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.
    var prime = new Array(max_val + 1);
    prime.fill(true);
    // Remaining part of SIEVE
    prime[0] = false;
    prime[1] = false;
    for (var 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 (var i = p * 2; i <= max_val; i += p)
                prime[i] = false;
        }
    }
 
    var cnt = 0; // Initialize result
 
    // Traverse through the array
    for (var i = 0; i < n - 1; ++i) {
        var val = A[i];
        for (var j = i + 1; j < n; ++j) {
            val += A[j];
 
            if (prime[val])
                ++cnt;
        }
    }
 
    // return answer
    return cnt;
}
    var A = [ 1, 2, 3, 4, 5 ];
    var n =A.length;
 
document.write( primeSubarrays(A, n));
 
// This code is contributed by SoumikMondal
 
</script>

Output

Complexity Analysis:

Time Complexity: O(nlog(logn))
Auxiliary Space: O(max_val)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!