Encuentre el subarreglo más largo con la suma principal en un arreglo dado

Dado un arreglo arr [], la tarea es encontrar el subarreglo más largo cuya suma sea un número primo .

Ejemplos:

Entrada:   arr[ ] = {1, 4, 2, 1}
Salida:  3
Explicación:  4+2+1=7 y 7 es un número primo, por lo que el subarreglo que obtenemos es {4, 2, 1}.

Entrada: arr[ ] = {5, 2, 11, 4, 7, 19}
Salida:  5
Explicación:  5+2+11+4+7=29 y 29 es un número primo, por lo que el subarreglo que obtenemos es {5, 2, 11, 4, 7, 19} .

Enfoque: este problema se puede resolver generando todos los subarreglos y verificando para cada subarreglo si la suma es prima o no. Para la comprobación de las impurezas se puede utilizar el Tamiz de Eratóstenes . Cualquier subarreglo puede tener una suma máxima igual a la suma de todos los elementos del arreglo original. Siga los pasos para resolver el problema dado.

• Cree una variable de total_sum que almacene la suma de todos los elementos en el arr[] .
• Haz la criba de Eratóstenes hasta suma_total porque ningún subarreglo puede tener una suma mayor que esa.
• Cree una variable max_sum para realizar un seguimiento del subarreglo máximo que obtenemos al generar todos los subarreglos.
• Use dos bucles para encontrar la suma de todos los subarreglos de arr[] y para cada subarreglo, verifique si la suma es prima o no.
• Toma el máximo entre aquellos subarreglos cuya suma es primo.
• Imprima max_sum como la respuesta requerida.

A continuación se muestra la implementación del enfoque anterior.

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Utility function to find whether number is
// prime or not
void SieveOfEratosthenes(
    vector<bool>& prime, int total_sum)
{
    // Create a boolean array "prime[0..n]" and
    // initialize all entries it as true.
    // A value in prime[i] will finally be false
    // if i is Not a prime, else true.
    for (int i = 0; i <= total_sum; i++) {
        prime[i] = true;
    }
 
    for (int p = 2; p * p <= total_sum; p++) {
 
        // If prime[p] is not changed,
        // then it is a prime
        if (prime[p] == true) {
 
            // Update all multiples of p
            // greater than or equal to the square
            // of it numbers which are multiple of p
            // and are less than p^2 are already
            // been marked.
            for (int i = p * p; i <= total_sum; i += p)
                prime[i] = false;
        }
    }
}
 
int maxLenSubarrayWithSumPrime(
    vector<int>& arr, int n)
{
    // to store total_sum of original array
    int total_sum = 0;
 
    // calculate total_sum
    for (int i = 0; i < n; i++) {
        total_sum += arr[i];
    }
 
    // to store whether the number is
    // prime or not
    vector<bool> prime(total_sum + 1);
 
    // calling sieve to get prime values
    SieveOfEratosthenes(prime, total_sum);
 
    // to keep track of current and
    // maximum sum till now
    int max_sum = 0, cur_sum = 0;
    for (int i = 0; i < n; i++) {
        cur_sum = 0;
        for (int j = i; j < n; j++) {
            cur_sum += arr[j];
 
            // is current sum is prime
            if (prime[cur_sum]) {
                max_sum = max(max_sum, j - i + 1);
            }
        }
    }
 
    // return maximum sum founded.
    return max_sum;
}
 
// Driver Code
int main()
{
    int n = 6;
    vector<int> arr = { 5, 2, 11, 4, 7, 19 };
 
    cout << maxLenSubarrayWithSumPrime(arr, n);
}

// Java program for above approach
import java.util.*;
 
class GFG{
 
// Utility function to find whether number is
// prime or not
static void SieveOfEratosthenes(
    boolean []prime, int total_sum)
{
   
    // Create a boolean array "prime[0..n]" and
    // initialize all entries it as true.
    // A value in prime[i] will finally be false
    // if i is Not a prime, else true.
    for (int i = 0; i <= total_sum; i++) {
        prime[i] = true;
    }
 
    for (int p = 2; p * p <= total_sum; p++) {
 
        // If prime[p] is not changed,
        // then it is a prime
        if (prime[p] == true) {
 
            // Update all multiples of p
            // greater than or equal to the square
            // of it numbers which are multiple of p
            // and are less than p^2 are already
            // been marked.
            for (int i = p * p; i <= total_sum; i += p)
                prime[i] = false;
        }
    }
}
 
static int maxLenSubarrayWithSumPrime(
    int[] arr, int n)
{
    // to store total_sum of original array
    int total_sum = 0;
 
    // calculate total_sum
    for (int i = 0; i < n; i++) {
        total_sum += arr[i];
    }
 
    // to store whether the number is
    // prime or not
    boolean []prime = new boolean[total_sum + 1];
 
    // calling sieve to get prime values
    SieveOfEratosthenes(prime, total_sum);
 
    // to keep track of current and
    // maximum sum till now
    int max_sum = 0, cur_sum = 0;
    for (int i = 0; i < n; i++) {
        cur_sum = 0;
        for (int j = i; j < n; j++) {
            cur_sum += arr[j];
 
            // is current sum is prime
            if (prime[cur_sum]) {
                max_sum = Math.max(max_sum, j - i + 1);
            }
        }
    }
 
    // return maximum sum founded.
    return max_sum;
}
 
// Driver Code
public static void main(String[] args)
{
    int n = 6;
    int []arr = { 5, 2, 11, 4, 7, 19 };
 
    System.out.print(maxLenSubarrayWithSumPrime(arr, n));
}
}
 
// This code is contributed by shikhasingrajput.

# Python 3 program for above approach
 
from math import sqrt
# Utility function to find whether number is
# prime or not
def SieveOfEratosthenes(prime, total_sum):
    # Create a boolean array "prime[0..n]" and
    # initialize all entries it as true.
    # A value in prime[i] will finally be false
    # if i is Not a prime, else true.
    for i in range(total_sum+1):
        prime[i] = True
 
    for p in range(2,int(sqrt(total_sum)),1):
        # If prime[p] is not changed,
        # then it is a prime
        if (prime[p] == True):
 
            # Update all multiples of p
            # greater than or equal to the square
            # of it numbers which are multiple of p
            # and are less than p^2 are already
            # been marked.
            for i in range(p * p,total_sum+1,p):
                prime[i] = False
 
def maxLenSubarrayWithSumPrime(arr, n):
    # to store total_sum of original array
    total_sum = 0
 
    # calculate total_sum
    for i in range(n):
        total_sum += arr[i]
 
    # to store whether the number is
    # prime or not
    prime = [ False for i in range(total_sum + 1)]
 
    # calling sieve to get prime values
    SieveOfEratosthenes(prime, total_sum)
 
    # to keep track of current and
    # maximum sum till now
    max_sum = 0
    cur_sum = 0
    for i in range(n):
        cur_sum = 0
        for j in range(i,n,1):
            cur_sum += arr[j]
 
            # is current sum is prime
            if (prime[cur_sum]):
                max_sum = max(max_sum, j - i + 1)
 
    # return maximum sum founded.
    return max_sum
 
# Driver Code
if __name__ == '__main__':
    n = 6
    arr = [5, 2, 11, 4, 7, 19]
    print(maxLenSubarrayWithSumPrime(arr, n))
     
    # This code is contributed by SURENDRA_GANGWAR.

// C# program for above approach
using System;
class GFG {
 
    // Utility function to find whether number is
    // prime or not
    static void SieveOfEratosthenes(bool[] prime,
                                    int total_sum)
    {
 
        // Create a boolean array "prime[0..n]" and
        // initialize all entries it as true.
        // A value in prime[i] will finally be false
        // if i is Not a prime, else true.
        for (int i = 0; i <= total_sum; i++) {
            prime[i] = true;
        }
 
        for (int p = 2; p * p <= total_sum; p++) {
 
            // If prime[p] is not changed,
            // then it is a prime
            if (prime[p] == true) {
 
                // Update all multiples of p
                // greater than or equal to the square
                // of it numbers which are multiple of p
                // and are less than p^2 are already
                // been marked.
                for (int i = p * p; i <= total_sum; i += p)
                    prime[i] = false;
            }
        }
    }
 
    static int maxLenSubarrayWithSumPrime(int[] arr, int n)
    {
        // to store total_sum of original array
        int total_sum = 0;
 
        // calculate total_sum
        for (int i = 0; i < n; i++) {
            total_sum += arr[i];
        }
 
        // to store whether the number is
        // prime or not
        bool[] prime = new bool[total_sum + 1];
 
        // calling sieve to get prime values
        SieveOfEratosthenes(prime, total_sum);
 
        // to keep track of current and
        // maximum sum till now
        int max_sum = 0, cur_sum = 0;
        for (int i = 0; i < n; i++) {
            cur_sum = 0;
            for (int j = i; j < n; j++) {
                cur_sum += arr[j];
 
                // is current sum is prime
                if (prime[cur_sum]) {
                    max_sum = Math.Max(max_sum, j - i + 1);
                }
            }
        }
 
        // return maximum sum founded.
        return max_sum;
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        int n = 6;
        int[] arr = { 5, 2, 11, 4, 7, 19 };
 
        Console.WriteLine(
            maxLenSubarrayWithSumPrime(arr, n));
    }
}
 
// This code is contributed by ukasp.

<script>
        // JavaScript Program to implement
        // the above approach
 
        // Utility function to find whether number is
        // prime or not
        function SieveOfEratosthenes(
            prime, total_sum)
        {
         
            // Create a boolean array "prime[0..n]" and
            // initialize all entries it as true.
            // A value in prime[i] will finally be false
            // if i is Not a prime, else true.
            for (let i = 0; i <= total_sum; i++) {
                prime[i] = true;
            }
 
            for (let p = 2; p * p <= total_sum; p++) {
 
                // If prime[p] is not changed,
                // then it is a prime
                if (prime[p] == true) {
 
                    // Update all multiples of p
                    // greater than or equal to the square
                    // of it numbers which are multiple of p
                    // and are less than p^2 are already
                    // been marked.
                    for (let i = p * p; i <= total_sum; i += p)
                        prime[i] = false;
                }
            }
            return prime;
        }
 
        function maxLenSubarrayWithSumPrime(
            arr, n)
        {
         
            // to store total_sum of original array
            let total_sum = 0;
 
            // calculate total_sum
            for (let i = 0; i < n; i++) {
                total_sum += arr[i];
            }
 
            // to store whether the number is
            // prime or not
            let prime = new Array(total_sum + 1);
            // calling sieve to get prime values
            prime = SieveOfEratosthenes(prime, total_sum);
 
            // to keep track of current and
            // maximum sum till now
            let max_sum = 0, cur_sum = 0;
            for (let i = 0; i < n; i++) {
                cur_sum = 0;
                for (let j = i; j < n; j++) {
                    cur_sum += arr[j];
 
                    // is current sum is prime
                    if (prime[cur_sum]) {
                        max_sum = Math.max(max_sum, j - i + 1);
                    }
                }
            }
 
            // return maximum sum founded.
            return max_sum;
        }
 
        // Driver Code
        let n = 6;
        let arr = [5, 2, 11, 4, 7, 19];
 
        document.write(maxLenSubarrayWithSumPrime(arr, n));
 
     // This code is contributed by Potta Lokesh
 
    </script>

5

Complejidad temporal: O(N^2) 
Complejidad auxiliar: O(N)