Count subarrays with Prime sum
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++ 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 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 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# 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
<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>
<?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
?>
Output
3
Complexity Analysis:
- Time Complexity: O(nlog(logn))
- Auxiliary Space: O(max_val)
Approach : Prefix Sum with Prime Check
This method uses a prefix sum array to reduce the time complexity of sum calculations.
Follow the below steps:
- Create a prefix sum array where prefix[i] is the sum of the array from the start to the i-th element.
- For every pair of indices (i, j) with i < j, calculate the subarray sum using the prefix sum array.
- Check if the sum is prime & count the valid subarrays.
- Return the count.
Below is the implementation of the above approach:
#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
def is_prime(n):
if n <= 1:
return False # Numbers less than or equal to 1 are not prime
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False # Found a divisor, so n is not prime
return True # No divisors found, so n is prime
def count_prime_sum_subarrays(A):
n = len(A)
prefix = [0] * (n + 1)
# Create prefix sum array
# prefix[i] will store the sum of elements from A[0] to A[i-1]
for i in range(n):
prefix[i + 1] = prefix[i] + A[i]
count = 0
# Check subarray sums using prefix array
# Consider all subarrays with size > 1
for i in range(n):
for j in range(i + 1, n):
# Calculate the sum of subarray A[i:j+1]
subarray_sum = prefix[j + 1] - prefix[i]
# Check if this sum is prime
if is_prime(subarray_sum):
count += 1 # Increment count if the sum is prime
return count
A = [22, 33, 4, 1, 10]
print(count_prime_sum_subarrays(A))
Output
4
Complexity Analysis:
- Time Complexity: O(n2 √m), where m is the maximum possible subarray sum due to prime checking.
- Auxiliary Space: O(n)