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 sumint 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 programint 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 Codeif __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 sumfunction 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
3
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
