Recuento de formas de seleccionar números primos o no primos según el índice de array

Dada una array A[] de tamaño N . Se debe crear una array utilizando la array dada considerando las siguientes condiciones.

• Si el índice es primo, debe elegir un número no primo que sea menor o igual que A[i] .
• Si el índice no es primo, debe elegir un número primo que sea menor o igual que A[i] .

La tarea es contar el número total de formas en que se pueden seleccionar dichos números.

Nota: La indexación de la array dada debe considerarse una indexación basada en 1.

Ejemplos:

Entrada: N = 5 A = {2, 3, 4, 8, 5}
Salida:  16
Explicación:  Puede elegir 1 número para el índice 1, es decir, 2 
(como el índice 1 no es primo y el número primo cuenta menor 
o igual que 2 es uno, es decir, 2), 1 número para el índice 2,  
2 números para el índice 3, 4 números para el índice 4 
y 2 números para el índice 5. 
Por lo tanto, el número total de vías = 1x1x2x4x2 = 16.

Entrada: N = 2 A = {5, 6}
Salida:  9
Explicación:   Puede elegir 3 números para el índice 1,  
3 números para el índice 2. Por lo tanto, número total de formas = 3×3 = 9 .

Planteamiento: La idea para resolver el problema es la siguiente:

• Contar y almacenar el valor de todos los primos y no primos en una array hasta el elemento máximo de la array. 
• Luego iteramos la array dada y luego, si el índice i no es primo, multiplicamos el recuento principal hasta A[i] y realizamos la operación similar para el índice principal.

Siga la siguiente ilustración para una mejor comprensión

Ilustración: 

Considere un ejemplo N = 5 y A[] = {2, 3, 4, 8, 5}

Como el índice 1 no es primo, el recuento de números primos menor o igual a 2 es 1 (es decir, 2) 
Como el índice 2 es primo, entonces el recuento de números no primos menor o igual a 3 es 1 (es decir, 1)
Como el índice 3 es primo El conteo de números no primos menor o igual a 4 es 2 (es decir, 1, 4)
Como el índice 4 es no primo Entonces, el conteo de números primos menor o igual a 8 es 4 (es decir, 2, 3, 5, 7)
Como el índice 5 es El recuento de números Prime So Non Prime menor o igual a 5 es 2 (es decir, 1, 4)

Número total de vías = 1 x 1 x 2 x 4 x 2 = 16 

Por lo tanto, el número total de formas de seleccionar el número de la array es 16 .      

Siga los pasos mencionados a continuación para implementar la idea.

• Encuentre el número máximo de la array dada.
• Iterar desde 1 hasta el valor máximo y encontrar el recuento de números primos y no primos hasta cada valor y almacenarlos en un vector de pares.
• Iterar sobre la array:
  • Compruebe si el índice actual es primo o no primo. si el índice actual es primo, seleccione el recuento de valores no primos del vector del par.
  • Multiplique la respuesta con el conteo no primo y almacene estos valores en la respuesta nuevamente.
  • Si el índice actual no es primo, seleccione el conteo de valores primos del vector de par y multiplique con la respuesta y almacene estos valores en la respuesta nuevamente.
• Devuelve la respuesta.

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

#include <bits/stdc++.h>
using namespace std;
  
// Funtion to check whether the number
// is prime or not
bool isPrime(int a)
{
    if (a == 1)
        return false;
    if (a == 2)
        return true;
    for (int i = 2; i <= sqrt(a); i++) {
        if (a % i == 0)
            return false;
    }
    return true;
}
  
// Funtion to count prime and non prime number
// and push count in vector
void count_prime_and_NonPrime(int n,
                              vector<pair<int, int> >& v)
{
    int p = 0, np = 0;
    v.push_back(make_pair(p, np));
    for (int i = 1; i <= n; i++) {
        if (isPrime(i))
            p++;
        else
            np++;
        v.push_back(make_pair(p, np));
    }
}
  
// Function to find number of ways
int NoOfWays(int n, int a[])
{
    vector<pair<int, int> > v;
    int mx = 0;
    for (int i = 0; i < n; i++) {
        mx = max(mx, a[i]);
    }
    count_prime_and_NonPrime(mx, v);
    int ans = 1;
    for (int j = 0; j < n; j++) {
        int prime = v[a[j]].first;
        int nonPrime = v[a[j]].second;
        if (isPrime(j + 1)) {
            ans *= nonPrime;
        }
        else {
            ans *= prime;
        }
    }
    return ans;
}
  
// Driver code
int main()
{
    int N = 5;
    int A[] = { 2, 3, 4, 8, 5 };
  
    // Function call
    cout << NoOfWays(N, A) << endl;
    return 0;
}

16

Complejidad de tiempo: O(N * sqrt(M)) donde M es el elemento más grande de la array
Espacio auxiliar: O(N)