Recuento de subconjuntos cuyo producto es múltiplo de primos únicos

Dada una array arr[] de tamaño N,  la tarea es contar el número de subconjuntos no vacíos cuyo producto es igual a P1×P2×P3×……..×Pk  donde P1, P2, P3, …….Pk son números primos distintos .

Ejemplos:

Entrada: arr[ ] = {2, 4, 7, 10}
Salida: 5
Explicación: Hay un total de 5 subconjuntos cuyo producto es el producto de números primos distintos.
Subconjunto 1: {2} -> 2
Subconjunto 2: {2, 7} -> 2×7
Subconjunto 3: {7} -> 7
Subconjunto 4: {7, 10} -> 2×5×7
Subconjunto 5: { 10} -> 2×5

Entrada: arr[ ] = {12, 9}
Salida: 0

Enfoque: la idea principal es encontrar los números que son productos de números primos distintos y llamar a la recursividad para incluirlos en el subconjunto o no incluirlos en el subconjunto. Además, un elemento solo se agrega al subconjunto si y solo si el GCD de todo el subconjunto después de agregar el elemento es 1. Siga los pasos a continuación para resolver el problema:

• Inicialice un dict , digamos, Freq, para almacenar la frecuencia de los elementos de la array.
• Inicialice una array , digamos, Unique[] y almacene todos aquellos elementos que son productos de solo números primos distintos .
• Llame a una función recursiva, diga Countprime(pos, curSubset) para contar todos esos subconjuntos.
• Caso base : si pos es igual al tamaño de la array única:
  • si curSubset está vacío, entonces devuelve 0
  • de lo contrario, devuelve el producto de las frecuencias de cada elemento de curSubset .
• Compruebe si el elemento en pos se puede tomar en el subconjunto actual o no
  • Si se toma, llame a las funciones recursivas como la suma de countPrime(pos+1, curSubset) y countPrime(pos+1, curSubset+[unique[pos]]).
  • de lo contrario, llame a countPrime(pos+1, curSubset).
• Imprime el ans devuelto por la función.

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

# Python program for the above approach
 
# Importing the module
from math import gcd, sqrt
 
# Function to check number has
# distinct prime
def checkDistinctPrime(n):
    original = n
    product = 1
 
    # While N has factors of
    # two
    if (n % 2 == 0):
        product *= 2
        while (n % 2 == 0):
            n = n//2
     
    # Traversing till sqrt(N)
    for i in range(3, int(sqrt(n)), 2):
       
        # If N has a factor of i
        if (n % i == 0):
            product = product * i
             
            # While N has a factor
            # of i
            while (n % i == 0):
                n = n//i
 
    # Covering case, N is Prime
    if (n > 2):
        product = product * n
 
    return product == original
 
 
# Function to check whether num
# can be added to the subset
def check(pos, subset, unique):
    for num in subset:
        if gcd(num, unique[pos]) != 1:
            return False
    return True
 
 
# Recursive Function to count subset
def countPrime(pos, currSubset, unique, frequency):
 
    # Base Case
    if pos == len(unique):
         
        # If currSubset is empty
        if not currSubset:
            return 0
 
        count = 1
        for element in currSubset:
            count *= frequency[element]
        return count
 
    # If Unique[pos] can be added to
    # the Subset
    if check(pos, currSubset, unique):
        return countPrime(pos + 1, currSubset, \
                          unique, frequency)\
             + countPrime(pos + 1, currSubset+[unique[pos]], \
                          unique, frequency)
    else:
        return countPrime(pos + 1, currSubset, \
                          unique, frequency)
   
# Function to count the subsets
def countSubsets(arr, N):
   
    # Initialize unique
    unique = set()
    for element in arr:
        # Check it is a product of
        # distinct primes
        if checkDistinctPrime(element):
            unique.add(element)
 
    unique = list(unique)
     
    # Count frequency of unique element
    frequency = dict()
    for element in unique:
        frequency[element] = arr.count(element)
 
    # Function Call
    ans = countPrime(0, [], unique, frequency)
    return ans
 
# Driver Code
if __name__ == "__main__":
 
    # Given Input
    arr = [2, 4, 7, 10]
    N = len(arr)
     
    # Function Call
    ans = countSubsets(arr, N)
    print(ans)

<script>
    // Javascript program for the above approach
     
    // Function to return
    // gcd of a and b
    function gcd(a, b)
    {
        if (a == 0)
            return b;
        return gcd(b % a, a);
    }
 
    // Function to check number has
    // distinct prime
    function checkDistinctPrime(n)
    {
        let original = n;
        let product = 1;
 
        // While N has factors of
        // two
        if (n % 2 == 0)
        {
            product *= 2;
            while (n % 2 == 0)
            {
                n = parseInt(n/2, 10);
            }
        }
 
        // Traversing till sqrt(N)
        for(let i = 3; i < parseInt(Math.sqrt(n), 10); i+=2)
        {
            // If N has a factor of i
            if (n % i == 0)
            {
                product = product * i;
 
                // While N has a factor of i
                while(n % i == 0)
                {
                    n = parseInt(n / i, 10);
                }
            }
        }
 
        // Covering case, N is Prime
        if (n > 2)
        {
            product = product * n;
        }
 
        return product == original;
    }
 
    // Function to check whether num
    // can be added to the subset
    function check(pos, subset, unique)
    {
        for(let num = 0; num < subset.length; num++)
        {
            if(gcd(subset[num], unique[pos]) != 1)
            {
                return false;
            }
        }
        return true;
    }
 
    // Recursive Function to count subset
    function countPrime(pos, currSubset, unique, frequency)
    {
        // Base Case
        if(pos == unique.length)
        {
            // If currSubset is empty
            if(currSubset.length == 0)
                return 0;
 
            count = 1;
            for(let element = 0; element < currSubset.length; element++)
            {
                count *= frequency[currSubset[element]];
            }
            return count;
        }
 
        // If Unique[pos] can be added to
        // the Subset
        if(check(pos, currSubset, unique))
        {
            return countPrime(pos + 1, currSubset, unique, frequency)
                 + countPrime(pos + 1, currSubset+[unique[pos]],
                              unique, frequency);
        }
        else
        {
            return countPrime(pos + 1, currSubset, unique, frequency);
        }
    }
 
    // Function to count the subsets
    function countSubsets(arr, N)
    {
        // Initialize unique
        let unique = new Set();
        for(let element = 0; element < arr.length; element++)
        {
            return 5;
            // Check it is a product of
            // distinct primes
            if(checkDistinctPrime(element))
            {
                unique.add(element);
            }
        }
 
        unique = Array.from(unique);
 
        // Count frequency of unique element
        let frequency = new Map();
        for(let element = 0; element < unique.length; element++)
        {
            let freq = 0;
            for(let i = 0; i < unique.length; i++)
            {
                if(unique[element] == unique[i])
                {
                    freq++;
                }
            }
            frequency[element] = freq;
        }
 
        // Function Call
        let ans = countPrime(0, [], unique, frequency);
        return ans;
    }
     
    // Given Input
    let arr = [2, 4, 7, 10];
    let N = arr.length;
       
    // Function Call
    let ans = countSubsets(arr, N);
    document.write(ans);
     
    // This code is contributed by divyesh072019.
</script>

5

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