Recuento de particiones multiplicativas de N

Dado un número entero N , la tarea es encontrar el número total de particiones multiplicativas para N.

Partición multiplicativa: número de formas de factorizar un número entero con todos los factores mayores que 1.
 

Ejemplos: 

Entrada: N = 20 
Salida: 4 
Explicación: Las 
particiones multiplicativas de 20 son: 
2 × 2 × 5 = 2 × 10 = 4 × 5 = 20.
Entrada: N = 30 
Salida: 5 
Explicación: Las 
particiones multiplicativas de 30 son: 
2 × 3 × 5 = 2 × 15 = 6 × 5 = 3 × 10 = 30 
 

Enfoque : la idea es probar con cada divisor de N y luego descomponer recursivamente el dividendo para obtener las particiones multiplicativas. A continuación se muestran las ilustraciones de los pasos del enfoque:

• Inicialice el factor mínimo como 2. Dado que es el factor mínimo distinto de 1.
• Comience un ciclo desde i = mínimo hasta N – 1, y verifique si el número divide a N y N/i > i, luego incremente el contador en 1 y vuelva a llamar a la misma función. Dado que i divide a n, significa que i y N/i se pueden factorizar algunas veces más.

Por ejemplo:

Si N = 30, sea i = min = 2 
30 % 2 = 0, entonces nuevamente recurra con (2, 15) 
15 % 3 = 0, entonces nuevamente recurra con (3, 5) 
. 
. 
y así. 
 

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

// C++ implementation to find
// the multiplicative partitions of
// the given number N
#include <bits/stdc++.h>
using namespace std;
 
// Function to return number of ways
// of factoring N with all
// factors greater than 1
static int getDivisors(int min, int n)
{
     
    // Variable to store number of ways
    // of factoring n with all
    // factors greater than 1
    int total = 0;
     
    for(int i = min; i < n; ++i)
    {
        if (n % i == 0 && n / i >= i)
        {
            ++total;
            if (n / i > i)
                total += getDivisors(i, n / i);
        }
    }
    return total;
}
 
// Driver code
int main()
{
    int n = 30;
     
    // 2 is the minimum factor of
    // number other than 1.
    // So calling recursive
    // function to find
    // number of ways of factoring N
    // with all factors greater than 1
    cout << 1 + getDivisors(2, n);
     
    return 0;
}
 
// This code is contributed by rutvik_56

// Java implementation to find
// the multiplicative partitions of
// the given number N
 
class MultiPart {
 
    // Function to return number of ways
    // of factoring N with all
    // factors greater than 1
    static int getDivisors(int min, int n)
    {
 
        // Variable to store number of ways
        // of factoring n with all
        // factors greater than 1
        int total = 0;
 
        for (int i = min; i < n; ++i)
 
            if (n % i == 0 && n / i >= i) {
                ++total;
                if (n / i > i)
                    total
                        += getDivisors(
                            i, n / i);
            }
 
        return total;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int n = 30;
 
        // 2 is the minimum factor of
        // number other than 1.
        // So calling recursive
        // function to find
        // number of ways of factoring N
        // with all factors greater than 1
        System.out.println(
            1 + getDivisors(2, n));
    }
}

# Python3 implementation to find
# the multiplicative partitions of
# the given number N
 
# Function to return number of ways
# of factoring N with all
# factors greater than 1
def getDivisors(min, n):
     
    # Variable to store number of ways
    # of factoring n with all
    # factors greater than 1
    total = 0
 
    for i in range(min, n):
        if (n % i == 0 and n // i >= i):
            total += 1
            if (n // i > i):
                total += getDivisors(i, n // i)
                 
    return total
 
# Driver code
if __name__ == '__main__':
   
    n = 30
 
    # 2 is the minimum factor of
    # number other than 1.
    # So calling recursive
    # function to find
    # number of ways of factoring N
    # with all factors greater than 1
    print(1 + getDivisors(2, n))
 
# This code is contributed by mohit kumar 29

// C# implementation to find
// the multiplicative partitions of
// the given number N
using System;
 
class GFG{
     
// Function to return number of ways
// of factoring N with all
// factors greater than 1
static int getDivisors(int min, int n)
{
 
    // Variable to store number of ways
    // of factoring n with all
    // factors greater than 1
    int total = 0;
 
    for(int i = min; i < n; ++i)
        if (n % i == 0 && n / i >= i)
        {
            ++total;
            if (n / i > i)
                total+= getDivisors(i, n / i);
        }
 
    return total;
}
 
// Driver code
public static void Main()
{
    int n = 30;
 
    // 2 is the minimum factor of
    // number other than 1.
    // So calling recursive
    // function to find
    // number of ways of factoring N
    // with all factors greater than 1
    Console.Write(1 + getDivisors(2, n));
}
}
 
// This code is contributed by adityakumar27200

<script>
 
// Javascript implementation to find
// the multiplicative partitions of
// the given number N
 
// Function to return number of ways
// of factoring N with all
// factors greater than 1
function getDivisors(min, n)
{
     
    // Variable to store number of ways
    // of factoring n with all
    // factors greater than 1
    var total = 0;
     
    for(var i = min; i < n; ++i)
    {
        if (n % i == 0 && n / i >= i)
        {
            ++total;
            if (n / i > i)
                total += getDivisors(i, n / i);
        }
    }
    return total;
}
 
// Driver code
var n = 30;
 
// 2 is the minimum factor of
// number other than 1.
// So calling recursive
// function to find
// number of ways of factoring N
// with all factors greater than 1
document.write( 1 + getDivisors(2, n));
 
 
</script>

5

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(1)