Encuentre el enésimo número de mosaico

Dado un número entero N , la tarea es encontrar el N ^número de mosaico . Un número de Mosaico se puede expresar de la siguiente manera: 
Si N = A ^a * B ^b * C ^c … donde A , B , C .. son los factores primos de N entonces el N-ésimo número de Mosaico será A * a * B * b * C*c… .

Ejemplos: 

Entrada: N = 8 
Salida: 6 
8 se puede expresar como 2 ³ . 
Por lo tanto, el octavo ^número mosaico será 2 * 3 = 6

Entrada: N = 36 
Salida: 24 
36 se puede expresar como 2 ² * 3 ² . 
2 * 2 * 3 * 2 = 24 
 

Método: Tenemos que encontrar todos los factores primos y también las potencias de los factores en el número dividiendo el número por el factor hasta que el factor divida al número. El N ^número de Mosaico será entonces el producto de los factores primos encontrados y sus potencias.

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the nth mosaic number
int mosaic(int n)
{
    int i, ans = 1;
 
    // Iterate from 2 to the number
    for (i = 2; i <= n; i++) {
 
        // If i is the factor of n
        if (n % i == 0 && n > 0) {
            int count = 0;
 
            // Find the count where i^count
            // is a factor of n
            while (n % i == 0) {
 
                // Divide the number by i
                n /= i;
 
                // Increase the count
                count++;
            }
 
            // Multiply the answer with
            // count and i
            ans *= count * i;
        }
    }
 
    // Return the answer
    return ans;
}
 
// Driver code
int main()
{
    int n = 36;
    cout << mosaic(n);
 
    return 0;
}

// Java implementation of the approach
import java.io.*;
 
class GFG
{
     
// Function to return the nth mosaic number
static int mosaic(int n)
{
    int i, ans = 1;
 
    // Iterate from 2 to the number
    for (i = 2; i <= n; i++)
    {
 
        // If i is the factor of n
        if (n % i == 0 && n > 0)
        {
            int count = 0;
 
            // Find the count where i^count
            // is a factor of n
            while (n % i == 0)
            {
 
                // Divide the number by i
                n /= i;
 
                // Increase the count
                count++;
            }
 
            // Multiply the answer with
            // count and i
            ans *= count * i;
        }
    }
 
    // Return the answer
    return ans;
}
 
// Driver code
public static void main (String[] args)
{
     
    int n = 36;
    System.out.println (mosaic(n));
}
}
 
// This code is contributed by jit_t.

# Python3 implementation of the approach
 
# Function to return the nth mosaic number
def mosaic(n):
 
    i=0
    ans = 1
 
    # Iterate from 2 to the number
    for i in range(2,n+1):
 
        # If i is the factor of n
        if (n % i == 0 and n > 0):
            count = 0
 
            # Find the count where i^count
            # is a factor of n
            while (n % i == 0):
 
                # Divide the number by i
                n //= i
 
                # Increase the count
                count+=1
             
 
            # Multiply the answer with
            # count and i
            ans *= count * i
         
 
    # Return the answer
    return ans
 
# Driver code
 
n = 36
print(mosaic(n))
 
# This code is contributed by mohit kumar 29

// C# implementation of the approach
using System;
 
class GFG
{
     
// Function to return the nth mosaic number
static int mosaic(int n)
{
    int i, ans = 1;
 
    // Iterate from 2 to the number
    for (i = 2; i <= n; i++)
    {
 
        // If i is the factor of n
        if (n % i == 0 && n > 0)
        {
            int count = 0;
 
            // Find the count where i^count
            // is a factor of n
            while (n % i == 0)
            {
 
                // Divide the number by i
                n /= i;
 
                // Increase the count
                count++;
            }
 
            // Multiply the answer with
            // count and i
            ans *= count * i;
        }
    }
 
    // Return the answer
    return ans;
}
 
// Driver code
static public void Main ()
{
    int n = 36;
    Console.WriteLine(mosaic(n));
}
}
 
// This code is contributed by ajit..

<script>
 
// Javascript implementation of the approach
 
// Function to return the nth mosaic number
function mosaic(n)
{
    let i, ans = 1;
 
    // Iterate from 2 to the number
    for(i = 2; i <= n; i++)
    {
         
        // If i is the factor of n
        if (n % i == 0 && n > 0)
        {
            let count = 0;
 
            // Find the count where i^count
            // is a factor of n
            while (n % i == 0)
            {
                 
                // Divide the number by i
                n = parseInt(n / i, 10);
 
                // Increase the count
                count++;
            }
 
            // Multiply the answer with
            // count and i
            ans *= count * i;
        }
    }
 
    // Return the answer
    return ans;
}
 
// Driver code
let n = 36;
document.write(mosaic(n));
 
// This code is contributed by mukesh07
 
</script>

24

Complejidad de tiempo: O (logn)

Espacio Auxiliar: O(1)