Factores primos distintos del producto de array

Dada una array de enteros. Digamos que P es el producto de los elementos de la array. Encuentre el número de factores primos distintos del producto P.

Ejemplos: 

Entrada: 1 2 3 4 5 
Salida: 3 
Explicación: Aquí P = 1 * 2 * 3 * 4 * 5 = 120. Los divisores primos distintos de 120 son 2, 3 y 5. Entonces, la salida es 3.

Entrada: 21 30 15 24 16 
Salida: 4 
Explicación: Aquí P = 21 * 30 * 15 * 24 * 16 = 3628800. Los divisores primos distintos de 3628800 son 2, 3, 5 y 7. Entonces, la salida es 4.

Enfoque ingenuo: 
la solución simple para el problema sería multiplicar cada número en la array y luego encontrar el número de factores primos distintos del producto. 
Pero este método puede provocar un desbordamiento de enteros.

Mejor enfoque: 
para evitar el desbordamiento en lugar de multiplicar los números, podemos encontrar los factores primos de cada elemento por separado y almacenar los factores primos en un conjunto o un mapa para factores únicos.

// C++ program to count distinct prime
// factors of a number.
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the number of distinct prime
// factors of product of array
int Distinct_Prime_factors(vector<int> a)
{
    // use set to store distinct factors
    unordered_set<int> m;
 
    // iterate over every element of array
    for (int i = 0; i < a.size(); i++) {
        int sq = sqrt(a[i]);
 
        // from 2 to square root of number run
        // a loop and check the numbers which
        // are factors.
        for (int j = 2; j <= sq; j++) {
            if (a[i] % j == 0) {
 
                // if j is a factor store it in the set
                m.insert(j);
 
                // divide the number with j till it
                // is divisible so that only prime factors
                // are stored
                while (a[i] % j == 0) {
                    a[i] /= j;
                }
            }
        }
 
        // if the number is still greater than 1 then
        // it is a prime factor, insert in set
        if (a[i] > 1) {
            m.insert(a[i]);
        }
    }
 
    // the number of unique prime factors will
    // the size of the set
    return m.size();
}
 
// Driver Function
int main()
{
    vector<int> a = { 1, 2, 3, 4, 5 };
    cout << Distinct_Prime_factors(a) << '\n';
    return 0;
}

// Java program to count distinct
// prime factors of a number.
import java.util.*;
 
class GFG {
 
    // Function to count the number
    // of distinct prime factors of
    // product of array
    static int Distinct_Prime_factors(Vector<Integer> a)
    {
        // use set to store distinct factors
        HashSet<Integer> m = new HashSet<Integer>();
 
        // iterate over every element of array
        for (int i = 0; i < a.size(); i++) {
            int sq = (int)Math.sqrt(a.get(i));
 
            // from 2 to square root of number
            // run a loop and check the numbers
            // which are factors.
            for (int j = 2; j <= sq; j++) {
                if (a.get(i) % j == 0) {
 
                    // if j is a factor store
                    // it in the set
                    m.add(j);
 
                    // divide the number with j
                    // till it is divisible so
                    // that only prime factors
                    // are stored
                    while (a.get(i) % j == 0) {
                        a.set(i, a.get(i) / j);
                    }
                }
            }
 
            // if the number is still greater
            // than 1 then it is a prime factor,
            // insert in set
            if (a.get(i) > 1) {
                m.add(a.get(i));
            }
        }
 
        // the number of unique prime
        // factors will the size of the set
        return m.size();
    }
 
    // Driver Code
    public static void main(String args[])
    {
        Vector<Integer> a = new Vector<Integer>();
        a.add(1);
        a.add(2);
        a.add(3);
        a.add(4);
        a.add(5);
        System.out.println(Distinct_Prime_factors(a));
    }
}
 
// This code is contributed by Arnab Kundu

# Python3 program to count distinct
# prime factors of a number
import math
 
# Function to count the number of distinct
# prime factors of product of array
def Distinct_Prime_factors( a):
     
    # use set to store distinct factors
    m = []
 
    # iterate over every element of array
    for i in range (len(a)) :
        sq = int(math.sqrt(a[i]))
 
        # from 2 to square root of number run
        # a loop and check the numbers which
        # are factors.
        for j in range(2, sq + 1) :
            if (a[i] % j == 0) :
 
                # if j is a factor store
                # it in the set
                m.append(j)
 
                # divide the number with j till it
                # is divisible so that only prime
                # factors are stored
                while (a[i] % j == 0) :
                    a[i] //= j
 
        # if the number is still greater
        # than 1 then it is a prime factor,
        # insert in set
        if (a[i] > 2) :
            m.append(a[i])
 
    # the number of unique prime factors
    # will the size of the set
    return len(m)
 
# Driver Code
if __name__ == "__main__":
 
    a = [ 1, 2, 3, 4, 5 ]
    print (Distinct_Prime_factors(a))
 
# This code is contributed by ita_c

// C# program to count distinct
// prime factors of a number.
using System;
using System.Collections.Generic;
 
class GFG {
 
    // Function to count the number
    // of distinct prime factors of
    // product of array
    static int Distinct_Prime_factors(List<int> a)
    {
        // use set to store distinct factors
        HashSet<int> m = new HashSet<int>();
 
        // iterate over every element of array
        for (int i = 0; i < a.Count; i++) {
            int sq = (int)Math.Sqrt(a[i]);
 
            // from 2 to square root of number
            // run a loop and check the numbers
            // which are factors.
            for (int j = 2; j <= sq; j++) {
                if (a[i] % j == 0) {
 
                    // if j is a factor store
                    // it in the set
                    m.Add(j);
 
                    // divide the number with j
                    // till it is divisible so
                    // that only prime factors
                    // are stored
                    while (a[i] % j == 0) {
                        a[i] = a[i] / j;
                    }
                }
            }
 
            // if the number is still greater
            // than 1 then it is a prime factor,
            // insert in set
            if (a[i] > 1) {
                m.Add(a[i]);
            }
        }
 
        // the number of unique prime
        // factors will the size of the set
        return m.Count;
    }
 
    // Driver Code
    public static void Main()
    {
        List<int> a = new List<int>();
        a.Add(1);
        a.Add(2);
        a.Add(3);
        a.Add(4);
        a.Add(5);
        Console.WriteLine(Distinct_Prime_factors(a));
    }
}
 
// This code is contributed by ihritik

<script>
 
// Javascript program to count distinct
// prime factors of a number.   
 
// Function to count the number
// of distinct prime factors of
// product of array
function Distinct_Prime_factors(a)
{
     
    // Use set to store distinct factors
    let m = new Set();
 
    // Iterate over every element of array
    for(let i = 0; i < a.length; i++)
    {
        let sq = Math.floor(Math.sqrt(a[i]));
 
        // From 2 to square root of number
        // run a loop and check the numbers
        // which are factors.
        for(let j = 2; j <= sq; j++)
        {
            if (a[i] % j == 0)
            {
                 
                // If j is a factor store
                // it in the set
                m.add(j);
                 
                // Divide the number with j
                // till it is divisible so
                // that only prime factors
                // are stored
                while (a[i] % j == 0)
                {
                    a[i]= Math.floor(a[i] / j);
                }
            }
        }
 
        // If the number is still greater
        // than 1 then it is a prime factor,
        // insert in set
        if (a[i] > 1)
        {
            m.add(a[i]);
        }
    }
 
    // The number of unique prime
    // factors will the size of the set
    return m.size;
}
 
// Driver Code
let a = [ 1, 2, 3, 4, 5 ];
document.write(Distinct_Prime_factors(a));
 
// This code is contributed by avanitrachhadiya2155
 
</script>

Producción : 

3