Conteo de subarreglos que consisten solo en números primos

Dada una array A[] de longitud N , la tarea es encontrar el número de subarreglos formados únicamente por números primos.

Ejemplos:

Entrada: arr[] = {2, 3, 4, 5, 7} 
Salida: 6 
Explicación: 
Todos los subarreglos posibles formados solo por números primos son {{2}, {3}, {2, 3}, {5} , {7}, {5, 7}}

Entrada: arr[] = {2, 3, 5, 6, 7, 11, 3, 5, 9, 3} 
Salida: 17

Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los subarreglos posibles a partir del arreglo dado y verificar si está compuesto solo por números primos o no. 

Complejidad de Tiempo: O(N ³ * √max(array)), donde √M es el tiempo requerido para verificar si un número es primo o no y este M puede variar [min(arr), max(arr)] 

Espacio Auxiliar: O(1)

Enfoque de dos punteros: 

Tome dos punteros ‘i’ y ‘j’ apuntando al primer elemento de la array (arr[0] ). Inicialice ans a 0. Si el elemento en el índice ‘j’ es un número primo, entonces aumente ans en 1 e incremente j en 1. Si el elemento en el índice ‘j’ no es un número primo, incremente ‘i’ en 1 y actualice el valor de j a i. Repita los pasos anteriores hasta que ‘i’ llegue al final de la array. Regresar respuesta .

La implementación del método dado se muestra a continuación.

// C++ program to implement the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
bool is_prime(int n)
{
    if (n <= 1)
        return 0;
 
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0)
            return 0;
    }
 
    return 1;
}
 
int count_prime_subarrays(int arr[], int n)
{
    int ans = 0;
    int i = 0;
    int j = 0;
    while (i < n) {
        // If 'j' reaches the end of array but 'i' does not
        // , then change the value of 'j' to 'i'
        if (j == n) {
            i++;
            j = i;
            if (i
                == n) // if both 'i' and 'j' reaches the end
                      // of array, we will break the loop
                break;
        }
 
        if (is_prime(arr[j])) {
            ans++; // we will increment the count if 'j' is
                   // prime
            j++; // we will increment 'j' by 1
        }
        // if arr[j] is not prime
        else {
            i++; // we will increment i by 1
            j = i; // assign the value of i to j
        }
    }
 
    return ans;
}
 
// Driver Code
int main()
{
    int N = 10;
    int ar[] = { 2, 3, 5, 6, 7, 11, 3, 5, 9, 3 };
    cout << count_prime_subarrays(ar, N);
}

17

Enfoque eficiente: es necesario hacer la siguiente observación para optimizar el enfoque anterior:

El recuento de subarreglos de un arreglo de longitud M es igual a M * (M + 1) / 2 .

Por lo tanto, a partir de un arreglo dado, un subarreglo contiguo de longitud M que consiste solo en números primos generará M * (M + 1) / 2 subarreglos de longitud.

Siga los pasos a continuación para resolver el problema:  

• Recorra la array y para cada elemento verifique si es primo o no .
• Por cada número primo encontrado, siga incrementando count .
• Para cada elemento no primo, actualice la respuesta requerida agregando count * (count + 1) / 2 y reinicie count a 0 .
• Finalmente, imprima el subarreglo requerido.

Debajo de la implementación del enfoque anterior: 

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if a number
// is prime or not.
bool is_prime(int n)
{
    if (n <= 1)
        return 0;
 
    for (int i = 2; i * i <= n; i++) {
 
        // If n has any factor other than 1,
        // then n is non-prime.
        if (n % i == 0)
            return 0;
    }
 
    return 1;
}
 
// Function to return the count of
// subarrays made up of prime numbers only
int count_prime_subarrays(int ar[], int n)
{
 
    // Stores the answer
    int ans = 0;
 
    // Stores the count of continuous
    // prime numbers in an array
    int count = 0;
 
    for (int i = 0; i < n; i++) {
 
        // If the current array
        // element is prime
        if (is_prime(ar[i]))
 
            // Increase the count
            count++;
        else {
 
            if (count) {
 
                // Update count of subarrays
                ans += count * (count + 1)
                       / 2;
                count = 0;
            }
        }
    }
 
    // If the array ended with a
    // continuous prime sequence
    if (count)
        ans += count * (count + 1) / 2;
 
    return ans;
}
 
// Driver Code
int main()
{
    int N = 10;
    int ar[] = { 2, 3, 5, 6, 7,
                 11, 3, 5, 9, 3 };
    cout << count_prime_subarrays(ar, N);
}

// Java Program to implement
// the above approach
import java.util.*;
class GFG{
 
// Function to check if a number
// is prime or not.
static boolean is_prime(int n)
{
    if (n <= 1)
         return false;
 
    for (int i = 2; i * i <= n; i++)
    {
 
        // If n has any factor other than 1,
        // then n is non-prime.
        if (n % i == 0)
             return false; 
    }
    return true;
}
 
// Function to return the count of
// subarrays made up of prime numbers only
static int count_prime_subarrays(int ar[], int n)
{
 
    // Stores the answer
    int ans = 0;
 
    // Stores the count of continuous
    // prime numbers in an array
    int count = 0;
 
    for (int i = 0; i < n; i++)
    {
 
        // If the current array
        // element is prime
        if (is_prime(ar[i]))
 
            // Increase the count
            count++;
        else
        {
            if (count != 0)
            {
 
                // Update count of subarrays
                ans += count * (count + 1) / 2;
                count = 0;
            }
        }
    }
 
    // If the array ended with a
    // continuous prime sequence
    if (count != 0)
        ans += count * (count + 1) / 2;
 
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 10;
    int []ar = { 2, 3, 5, 6, 7,
                11, 3, 5, 9, 3 };
    System.out.print(count_prime_subarrays(ar, N));
}
}
 
// This code is contributed by PrinciRaj1992

# Python3 program to implement
# the above approach
 
# Function to check if a number
# is prime or not.
def is_prime(n):
 
    if(n <= 1):
        return 0
 
    i = 2
    while(i * i <= n):
 
        # If n has any factor other than 1,
        # then n is non-prime.
        if(n % i == 0):
            return 0
 
        i += 1
 
    return 1
 
# Function to return the count of
# subarrays made up of prime numbers only
def count_prime_subarrays(ar, n):
 
    # Stores the answer
    ans = 0
 
    # Stores the count of continuous
    # prime numbers in an array
    count = 0
 
    for i in range(n):
 
        # If the current array
        # element is prime
        if(is_prime(ar[i])):
 
            # Increase the count
            count += 1
 
        else:
            if(count):
 
                # Update count of subarrays
                ans += count * (count + 1) // 2
                count = 0
 
    # If the array ended with a
    # continuous prime sequence
    if(count):
        ans += count * (count + 1) // 2
 
    return ans
 
# Driver Code
N = 10
ar = [ 2, 3, 5, 6, 7,
       11, 3, 5, 9, 3 ]
 
# Function call
print(count_prime_subarrays(ar, N))
 
# This code is contributed by Shivam Singh

// C# Program to implement
// the above approach
using System;
class GFG{
 
// Function to check if a number
// is prime or not.
static bool is_prime(int n)
{
    if (n <= 1)
         return false;
 
    for (int i = 2; i * i <= n; i++)
    {
 
        // If n has any factor other than 1,
        // then n is non-prime.
        if (n % i == 0)
             return false; 
    }
    return true;
}
 
// Function to return the count of
// subarrays made up of prime numbers only
static int count_prime_subarrays(int []ar, int n)
{
 
    // Stores the answer
    int ans = 0;
 
    // Stores the count of continuous
    // prime numbers in an array
    int count = 0;
 
    for (int i = 0; i < n; i++)
    {
 
        // If the current array
        // element is prime
        if (is_prime(ar[i]))
 
            // Increase the count
            count++;
        else
        {
            if (count != 0)
            {
 
                // Update count of subarrays
                ans += count * (count + 1) / 2;
                count = 0;
            }
        }
    }
 
    // If the array ended with a
    // continuous prime sequence
    if (count != 0)
        ans += count * (count + 1) / 2;
 
    return ans;
}
 
// Driver Code
public static void Main(String[] args)
{
    int N = 10;
    int []ar = { 2, 3, 5, 6, 7,
                11, 3, 5, 9, 3 };
    Console.Write(count_prime_subarrays(ar, N));
}
}
 
// This code is contributed by Rajput-Ji

<script>
 
      // JavaScript Program to implement
      // the above approach
 
      // Function to check if a number
      // is prime or not.
      function is_prime(n) {
        if (n <= 1) return 0;
 
        for (var i = 2; i * i <= n; i++) {
           
          // If n has any factor other than 1,
          // then n is non-prime.
          if (n % i == 0) return 0;
        }
 
        return 1;
      }
 
      // Function to return the count of
      // subarrays made up of prime numbers only
      function count_prime_subarrays(ar, n) {
        // Stores the answer
        var ans = 0;
 
        // Stores the count of continuous
        // prime numbers in an array
        var count = 0;
 
        for (var i = 0; i < n; i++) {
          // If the current array
          // element is prime
          if (is_prime(ar[i]))
            // Increase the count
            count++;
          else {
            if (count) {
              // Update count of subarrays
              ans += (count * (count + 1)) / 2;
              count = 0;
            }
          }
        }
 
        // If the array ended with a
        // continuous prime sequence
        if (count) ans += (count * (count + 1)) / 2;
 
        return ans;
      }
 
      // Driver Code
 
      var N = 10;
      var ar = [2, 3, 5, 6, 7, 11, 3, 5, 9, 3];
      document.write(count_prime_subarrays(ar, N));
       
</script>

17

Complejidad Temporal: O(N * √max(arr)), donde √M es el tiempo necesario para comprobar si un número es primo o no y este M puede variar [min(arr), max(arr)]  
Espacio Auxiliar: O (1)