Recuento de subarreglos que tienen exactamente K números primos

Dada una array arr[] de N enteros y un número K . La tarea es contar el número de subarreglo con exactamente K números primos .
Ejemplo: 
 

Entrada: arr[] = {1, 2, 3, 4}, K = 2 
Salida: 4 
Explicación: 
Dado que el número total de números primos en la array es 2, los 4 subarreglo con 2 números primos son: 
1. {2 , 3} 
2. {1, 2, 3} 
3. {2, 3, 4} 
4. {1, 2, 3, 4}
Entrada: arr[] = {2, 4, 5}, K = 3 
Salida : 0 
Explicación: 
Dado que el número total de números primos en la array es 2, que es menor que K (K = 3). 
Entonces no existe tal subarreglo con K primos. 
 

Acercarse: 
 

1. Recorra la array dada arr[] y verifique si el elemento es primo o no .
2. Si el elemento actual es primo, cambie el valor de la array de ese índice a 1, de lo contrario, cambie el valor en ese índice a 0.
3. Ahora la array dada se convierte en array binaria.
4. Encuentre el recuento de subarreglo con suma igual a K en el Array binario anterior utilizando el enfoque discutido en este artículo.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// A utility function to check if
// the number n is prime or not
bool isPrime(int n)
{
    int i;
 
    // Base Cases
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
 
    // Check to skip middle five
    // numbers in below loop
    if (n % 2 == 0 || n % 3 == 0) {
        return false;
    }
 
    for (i = 5; i * i <= n; i += 6) {
 
        // If n is divisible by i & i+2
        // then it is not prime
        if (n % i == 0
            || n % (i + 2) == 0) {
            return false;
        }
    }
 
    return true;
}
 
// Function to find number of subarrays
// with sum exactly equal to k
int findSubarraySum(int arr[], int n, int K)
{
    // STL map to store number of subarrays
    // starting from index zero having
    // particular value of sum.
    unordered_map<int, int> prevSum;
 
    int res = 0;
 
    // To store the sum of element traverse
    // so far
    int currsum = 0;
 
    for (int i = 0; i < n; i++) {
 
        // Add current element to currsum
        currsum += arr[i];
 
        // If currsum = K, then a new
        // subarray is found
        if (currsum == K) {
            res++;
        }
 
        // If currsum > K then find the
        // no. of subarrays with sum
        // currsum - K and exclude those
        // subarrays
        if (prevSum.find(currsum - K)
            != prevSum.end())
            res += (prevSum[currsum - K]);
 
        // Add currsum to count of
        // different values of sum
        prevSum[currsum]++;
    }
 
    // Return the final result
    return res;
}
 
// Function to count the subarray with K primes
void countSubarray(int arr[], int n, int K)
{
    // Update the array element
    for (int i = 0; i < n; i++) {
 
        // If current element is prime
        // then update the arr[i] to 1
        if (isPrime(arr[i])) {
            arr[i] = 1;
        }
 
        // Else change arr[i] to 0
        else {
            arr[i] = 0;
        }
    }
 
    // Function Call
    cout << findSubarraySum(arr, n, K);
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 4 };
    int K = 2;
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    countSubarray(arr, N, K);
    return 0;
}

// Java program for the above approach
 
import java.util.*;
 
class GFG {
 
    // A utility function to check if
    // the number n is prime or not
    static boolean isPrime(int n) {
        int i;
 
        // Base Cases
        if (n <= 1)
            return false;
        if (n <= 3)
            return true;
 
        // Check to skip middle five
        // numbers in below loop
        if (n % 2 == 0 || n % 3 == 0) {
            return false;
        }
 
        for (i = 5; i * i <= n; i += 6) {
 
            // If n is divisible by i & i+2
            // then it is not prime
            if (n % i == 0 || n % (i + 2) == 0) {
                return false;
            }
        }
 
        return true;
    }
 
    // Function to find number of subarrays
    // with sum exactly equal to k
    static int findSubarraySum(int arr[], int n, int K)
    {
        // STL map to store number of subarrays
        // starting from index zero having
        // particular value of sum.
        HashMap<Integer, Integer> prevSum =
             new HashMap<Integer, Integer>();
 
        int res = 0;
 
        // To store the sum of element traverse
        // so far
        int currsum = 0;
 
        for (int i = 0; i < n; i++) {
 
            // Add current element to currsum
            currsum += arr[i];
 
            // If currsum = K, then a new
            // subarray is found
            if (currsum == K) {
                res++;
            }
 
            // If currsum > K then find the
            // no. of subarrays with sum
            // currsum - K and exclude those
            // subarrays
            if (prevSum.containsKey(currsum - K)) {
                res += (prevSum.get(currsum - K));
            }
            // Add currsum to count of
            // different values of sum
            if (prevSum.containsKey(currsum))
                prevSum.put(currsum, prevSum.get(currsum) + 1);
            else
                prevSum.put(currsum, 1);
        }
 
        // Return the final result
        return res;
    }
 
    // Function to count the subarray with K primes
    static void countSubarray(int arr[], int n, int K) {
        // Update the array element
        for (int i = 0; i < n; i++) {
 
            // If current element is prime
            // then update the arr[i] to 1
            if (isPrime(arr[i])) {
                arr[i] = 1;
            }
 
            // Else change arr[i] to 0
            else {
                arr[i] = 0;
            }
        }
 
        // Function Call
        System.out.print(findSubarraySum(arr, n, K));
    }
 
    // Driver Code
    public static void main(String[] args) {
        int arr[] = { 1, 2, 3, 4 };
        int K = 2;
        int N = arr.length;
 
        // Function Call
        countSubarray(arr, N, K);
    }
}
 
// This code contributed by Rajput-Ji

# Python3 program for the above approach
from math import sqrt
 
 
# A utility function to check if
# the number n is prime or not
def isPrime(n):
    # Base Cases
    if (n <= 1):
        return False
    if (n <= 3):
        return True
 
    # Check to skip middle five
    # numbers in below loop
    if (n % 2 == 0 or n % 3 == 0):
        return False
 
    for i in range(5,int(sqrt(n))+1,6):
        # If n is divisible by i & i+2
        # then it is not prime
        if (n % i == 0 or n % (i + 2) == 0):
            return False
 
    return True
 
# Function to find number of subarrays
# with sum exactly equal to k
def findSubarraySum(arr,n,K):
    # STL map to store number of subarrays
    # starting from index zero having
    # particular value of sum.
    prevSum = {i:0 for i in range(100)}
 
    res = 0
 
    # To store the sum of element traverse
    # so far
    currsum = 0
 
    for i in range(n):
        # Add current element to currsum
        currsum += arr[i]
 
        # If currsum = K, then a new
        # subarray is found
        if (currsum == K):
            res += 1
 
        # If currsum > K then find the
        # no. of subarrays with sum
        # currsum - K and exclude those
        # subarrays
        if (currsum - K) in prevSum:
            res += (prevSum[currsum - K])
 
        # Add currsum to count of
        # different values of sum
        prevSum[currsum] += 1
 
    # Return the final result
    return res
 
# Function to count the subarray with K primes
def countSubarray(arr,n,K):
    # Update the array element
    for i in range(n):
        # If current element is prime
        # then update the arr[i] to 1
        if (isPrime(arr[i])):
            arr[i] = 1
 
        # Else change arr[i] to 0
        else:
            arr[i] = 0
 
    # Function Call
    print(findSubarraySum(arr, n, K))
 
# Driver Code
if __name__ == '__main__':
    arr =  [1, 2, 3, 4]
    K = 2
    N = len(arr)
 
    # Function Call
    countSubarray(arr, N, K)
 
# This code is contributed by Surendra_Gangwar

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// A utility function to check if
// the number n is prime or not
static bool isPrime(int n)
{
    int i;
 
    // Base Cases
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
 
    // Check to skip middle five
    // numbers in below loop
    if (n % 2 == 0 || n % 3 == 0)
    {
        return false;
    }
 
    for(i = 5; i * i <= n; i += 6)
    {
        
       // If n is divisible by i & i+2
       // then it is not prime
       if (n % i == 0 || n % (i + 2) == 0)
       {
           return false;
       }
    }
    return true;
}
 
// Function to find number of subarrays
// with sum exactly equal to k
static int findSubarraySum(int []arr, int n,
                                      int K)
{
     
    // STL map to store number of subarrays
    // starting from index zero having
    // particular value of sum.
    Dictionary<int, int> prevSum = new Dictionary<int, int>();
     
    int res = 0;
 
    // To store the sum of element traverse
    // so far
    int currsum = 0;
 
    for(int i = 0; i < n; i++)
    {
        
       // Add current element to currsum
       currsum += arr[i];
        
       // If currsum = K, then a new
       // subarray is found
       if (currsum == K)
       {
           res++;
       }
        
       // If currsum > K then find the
       // no. of subarrays with sum
       // currsum - K and exclude those
       // subarrays
       if (prevSum.ContainsKey(currsum - K))
       {
           res += (prevSum[currsum - K]);
       }
        
       // Add currsum to count of
       // different values of sum
       if (prevSum.ContainsKey(currsum))
       {
           prevSum[currsum] = prevSum[currsum] + 1;
       }
       else
       {
           prevSum.Add(currsum, 1);
       }
    }
     
    // Return the readonly result
    return res;
}
 
// Function to count the subarray with K primes
static void countSubarray(int []arr, int n, int K)
{
     
    // Update the array element
    for(int i = 0; i < n; i++)
    {
        
       // If current element is prime
       // then update the arr[i] to 1
       if (isPrime(arr[i]))
       {
           arr[i] = 1;
       }
        
       // Else change arr[i] to 0
       else
       {
           arr[i] = 0;
       }
    }
     
    // Function Call
    Console.Write(findSubarraySum(arr, n, K));
}
 
// Driver Code
public static void Main(String[] args)
{
    int []arr = { 1, 2, 3, 4 };
    int K = 2;
    int N = arr.Length;
 
    // Function Call
    countSubarray(arr, N, K);
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// JavaScript program for the above approach
 
// A utility function to check if
// the number n is prime or not
function isPrime(n)
{
    let i;
 
    // Base Cases
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
 
    // Check to skip middle five
    // numbers in below loop
    if (n % 2 == 0 || n % 3 == 0) {
        return false;
    }
 
    for (i = 5; i * i <= n; i += 6) {
 
        // If n is divisible by i & i+2
        // then it is not prime
        if (n % i == 0
            || n % (i + 2) == 0) {
            return false;
        }
    }
 
    return true;
}
 
// Function to find number of subarrays
// with sum exactly equal to k
function findSubarraySum(arr, n, K)
{
    // STL map to store number of subarrays
    // starting from index zero having
    // particular value of sum.
    let prevSum = new Map();
 
    let res = 0;
 
    // To store the sum of element traverse
    // so far
    let currsum = 0;
 
    for (let i = 0; i < n; i++) {
 
        // Add current element to currsum
        currsum += arr[i];
 
        // If currsum = K, then a new
        // subarray is found
        if (currsum == K) {
            res++;
        }
 
        // If currsum > K then find the
        // no. of subarrays with sum
        // currsum - K and exclude those
        // subarrays
        if (prevSum.has(currsum - K))
            res += (prevSum.get(currsum - K));
 
        // Add currsum to count of
        // different values of sum
        if(prevSum.has(currsum)){
            prevSum.set(currsum, prevSum.get(currsum) + 1)
        }else{
            prevSum.set(currsum, 1)
        }
    }
 
    // Return the final result
    return res;
}
 
// Function to count the subarray with K primes
function countSubarray(arr, n, K)
{
    // Update the array element
    for (let i = 0; i < n; i++) {
 
        // If current element is prime
        // then update the arr[i] to 1
        if (isPrime(arr[i])) {
            arr[i] = 1;
        }
 
        // Else change arr[i] to 0
        else {
            arr[i] = 0;
        }
    }
 
    // Function Call
    document.write(findSubarraySum(arr, n, K));
}
 
// Driver Code
 
let arr = [ 1, 2, 3, 4 ];
let K = 2;
let N = arr.length;
 
// Function Call
countSubarray(arr, N, K);
 
// This code is contributed by _saurabh_jaiswal
 
</script>

4

Complejidad del tiempo: O(N*log(log(N)))

Espacio Auxiliar: O(N)