Dada una array A[] de enteros. La tarea es contar los subarreglos totales cuya suma es primo con ( tamaño > 1 ).
Ejemplos :
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
Enfoque: Genere todos los subarreglos posibles y almacene su suma en un vector . Iterar el vector y verificar si una suma es prima o no. SÍ incrementa el conteo.
Puede usar la criba de eratóstenes para comprobar si una suma es prima en O(1).
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
3
Complejidad del tiempo: O(nlog(logn))
Espacio Auxiliar: O(max_val)
Publicación traducida automáticamente
Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA