Producto de cada K-ésimo número primo en una array

Dado un entero ‘k’ y una array de enteros ‘arr’ (menos de 10^6), la tarea es encontrar el producto de cada K-ésimo número primo en la array.
Ejemplos: 
 

Entrada: arr = {2, 3, 5, 7, 11}, k = 2 
Salida: 21 
Todos los elementos del arreglo son primos. Entonces, los números primos después de cada intervalo K (es decir, 2) son 3, 7 y su producto es 21. 
Entrada: arr = {41, 23, 12, 17, 18, 19}, k = 2 
Salida: 437 
 

Un enfoque simple: Recorra la array y encuentre cada K-ésimo número primo en la array y calcule el producto corriente. De esta manera, tendremos que verificar cada elemento de la array, ya sea que sea primo o no, lo que llevará más tiempo a medida que aumente el tamaño de la array.
Enfoque eficiente: Cree un tamiz que almacene si un número es primo o no. Entonces, se puede usar para comparar un número con primo en tiempo O(1). De esta manera, solo tenemos que realizar un seguimiento de cada número primo K’th y mantener el producto en ejecución.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000000
bool prime[MAX + 1];
void SieveOfEratosthenes()
{
    // Create a boolean array "prime[0..n]"
    // and initialize all the entries as true.
    // A value in prime[i] will finally be false
    // if i is Not a prime, else true.
    memset(prime, true, sizeof(prime));
 
    // 0 and 1 are not prime numbers
    prime[1] = false;
    prime[0] = false;
 
    for (int p = 2; p * p <= MAX; 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; i += p)
                prime[i] = false;
        }
    }
}
 
// compute the answer
void productOfKthPrimes(int arr[], int n, int k)
{
    // count of primes
    int c = 0;
 
    // product of the primes
    long long int product = 1;
 
    // traverse the array
    for (int i = 0; i < n; i++) {
 
        // if the number is a prime
        if (prime[arr[i]]) {
 
            // increase the count
            c++;
 
            // if it is the K'th prime
            if (c % k == 0) {
                product *= arr[i];
                c = 0;
            }
        }
    }
    cout << product << endl;
}
 
// Driver code
int main()
{
 
    // create the sieve
    SieveOfEratosthenes();
 
    int n = 5, k = 2;
 
    int arr[n] = { 2, 3, 5, 7, 11 };
 
    productOfKthPrimes(arr, n, k);
 
    return 0;
}

// Java implementation of the approach
 
class GFG
{
static int MAX=1000000;
static boolean[] prime=new boolean[MAX + 1];
static void SieveOfEratosthenes()
{
    // Create a boolean array "prime[0..n]"
    // and initialize all the entries as true.
    // A value in prime[i] will finally be false
    // if i is Not a prime, else true.
    //memset(prime, true, sizeof(prime));
 
    // 0 and 1 are not prime numbers
    prime[1] = true;
    prime[0] = true;
 
    for (int p = 2; p * p <= MAX; p++) {
 
        // If prime[p] is not changed,
        // then it is a prime
        if (prime[p] == false) {
 
            // Update all multiples of p
            for (int i = p * 2; i <= MAX; i += p)
                prime[i] = true;
        }
    }
}
 
// compute the answer
static void productOfKthPrimes(int arr[], int n, int k)
{
    // count of primes
    int c = 0;
 
    // product of the primes
    int product = 1;
 
    // traverse the array
    for (int i = 0; i < n; i++) {
 
        // if the number is a prime
        if (!prime[arr[i]]) {
 
            // increase the count
            c++;
 
            // if it is the K'th prime
            if (c % k == 0) {
                product *= arr[i];
                c = 0;
            }
        }
    }
    System.out.println(product);
}
 
// Driver code
public static void main(String[] args)
{
 
    // create the sieve
    SieveOfEratosthenes();
 
    int n = 5, k = 2;
  
    int[] arr=new int[]{ 2, 3, 5, 7, 11 };
  
    productOfKthPrimes(arr, n, k);
}
}
// This code is contributed by mits

# Python 3 implementation of the approach
 
MAX = 1000000
prime = [True]*(MAX + 1)
def SieveOfEratosthenes():
     
    # Create a boolean array "prime[0..n]"
    # and initialize all the entries as true.
    # A value in prime[i] will finally be false
    # if i is Not a prime, else true.
     
 
    # 0 and 1 are not prime numbers
    prime[1] = False;
    prime[0] = False;
 
    p = 2
    while p * p <= MAX:
 
        # If prime[p] is not changed,
        # then it is a prime
        if (prime[p] == True):
 
            # Update all multiples of p
            for i in range(p * 2, MAX+1, p):
                prime[i] = False
        p+=1
 
# compute the answer
def productOfKthPrimes(arr, n, k):
 
    # count of primes
    c = 0
 
    # product of the primes
    product = 1
 
    # traverse the array
    for i in range( n):
 
        # if the number is a prime
        if (prime[arr[i]]):
 
            # increase the count
            c+=1
 
            # if it is the K'th prime
            if (c % k == 0) :
                product *= arr[i]
                c = 0
 
    print(product)
 
# Driver code
if __name__ == "__main__":
 
    # create the sieve
    SieveOfEratosthenes()
 
    n = 5
    k = 2
 
    arr = [ 2, 3, 5, 7, 11 ]
 
    productOfKthPrimes(arr, n, k)
 
# This code is contributed by ChitraNayal

// C# implementation of the approach
class GFG
{
static int MAX = 1000000;
static bool[] prime = new bool[MAX + 1];
static void SieveOfEratosthenes()
{
    // Create a boolean array "prime[0..n]"
    // and initialize all the entries as
    // true. A value in prime[i] will
    // finally be false if i is Not a prime,
    // else true.
 
    // 0 and 1 are not prime numbers
    prime[1] = true;
    prime[0] = true;
 
    for (int p = 2; p * p <= MAX; p++)
    {
 
        // If prime[p] is not changed,
        // then it is a prime
        if (prime[p] == false)
        {
 
            // Update all multiples of p
            for (int i = p * 2;
                     i <= MAX; i += p)
                prime[i] = true;
        }
    }
}
 
// compute the answer
static void productOfKthPrimes(int[] arr,
                               int n, int k)
{
    // count of primes
    int c = 0;
 
    // product of the primes
    int product = 1;
 
    // traverse the array
    for (int i = 0; i < n; i++)
    {
 
        // if the number is a prime
        if (!prime[arr[i]])
        {
 
            // increase the count
            c++;
 
            // if it is the K'th prime
            if (c % k == 0)
            {
                product *= arr[i];
                c = 0;
            }
        }
    }
    System.Console.WriteLine(product);
}
 
// Driver code
static void Main()
{
 
    // create the sieve
    SieveOfEratosthenes();
 
    int n = 5, k = 2;
 
    int[] arr=new int[]{ 2, 3, 5, 7, 11 };
 
    productOfKthPrimes(arr, n, k);
}
}
 
// This code is contributed by mits

<script>
// Javascript implementation of the approach
 
let MAX = 1000000;
let prime = new Array(MAX + 1);
function SieveOfEratosthenes() {
    // Create a boolean array "prime[0..n]"
    // and initialize all the entries as true.
    // A value in prime[i] will finally be false
    // if i is Not a prime, else true.
    prime.fill(true)
 
    // 0 and 1 are not prime numbers
    prime[1] = false;
    prime[0] = false;
 
    for (let p = 2; p * p <= MAX; p++) {
 
        // If prime[p] is not changed,
        // then it is a prime
        if (prime[p] == true) {
 
            // Update all multiples of p
            for (let i = p * 2; i <= MAX; i += p)
                prime[i] = false;
        }
    }
}
 
// compute the answer
function productOfKthPrimes(arr, n, k) {
    // count of primes
    let c = 0;
 
    // product of the primes
    let product = 1;
 
    // traverse the array
    for (let i = 0; i < n; i++) {
 
        // if the number is a prime
        if (prime[arr[i]]) {
 
            // increase the count
            c++;
 
            // if it is the K'th prime
            if (c % k == 0) {
                product *= arr[i];
                c = 0;
            }
        }
    }
    document.write(product + "<br>");
}
 
// Driver code
 
// create the sieve
SieveOfEratosthenes();
 
let n = 5, k = 2;
 
let arr = [2, 3, 5, 7, 11];
 
productOfKthPrimes(arr, n, k);
 
// This code is contributed by gfgking.
</script>

21

Complejidad de tiempo : O(n)

Espacio Auxiliar: O(MAX)