Máximos divisores primos posibles que pueden existir en números que tienen exactamente N divisores

Dado un número entero N que denota el número de divisores de cualquier número, la tarea es encontrar el máximo de divisores primos posibles en un número que tiene N divisores.

Ejemplos: 

Entrada: N = 4 
Salida: 2

Entrada: N = 8 
Salida: 3 
 

Planteamiento: La idea es encontrar la descomposición en factores primos del número N, entonces la suma de las potencias de los divisores primos es el máximo posible de divisores primos de un número que puede tener con N divisores.

Por ejemplo:  

Let the number of divisors of number be 4,

Then the possible numbers can be 6, 10, 15,...
Divisors of 6 = 1, 2, 3, 6

Total number of prime-divisors = 2 (2, 3)

Prime Factorization of 4 = 22
Sum of powers of prime factors = 2

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

// C++ implementation to find the
// maximum possible prime divisor
// of a number can have N divisors
 
#include <iostream>
 
using namespace std;
 
#define ll long long int
 
// Function to find the
// maximum possible prime divisors
// of a number can have with N divisors
void findMaxPrimeDivisor(int n){
     
    int max_possible_prime = 0;
 
    // Number of time number
    // divided by 2
    while (n % 2 == 0) {
        max_possible_prime++;
        n = n / 2;
    }
 
    // Divide by other prime numbers
    for (int i = 3; i * i <= n; i = i + 2) {
        while (n % i == 0) {
            max_possible_prime++;
            n = n / i;
        }
    }
 
    // If the last number of also
    // prime then also include it
    if (n > 2) {
        max_possible_prime++;
    }
 
    cout << max_possible_prime << "\n";
}
 
// Driver Code
int main()
{
 
    int n = 4;
     
    // Function Call
    findMaxPrimeDivisor(n);
    return 0;
}

// Java implementation to find the
// maximum possible prime divisor
// of a number can have N divisors
import java.util.*;
 
class GFG{
 
// Function to find the
// maximum possible prime divisors
// of a number can have with N divisors
static void findMaxPrimeDivisor(int n)
{
    int max_possible_prime = 0;
 
    // Number of time number
    // divided by 2
    while (n % 2 == 0)
    {
        max_possible_prime++;
        n = n / 2;
    }
 
    // Divide by other prime numbers
    for(int i = 3; i * i <= n; i = i + 2)
    {
       while (n % i == 0)
       {
           max_possible_prime++;
           n = n / i;
       }
    }
 
    // If the last number of also
    // prime then also include it
    if (n > 2)
    {
        max_possible_prime++;
    }
    System.out.print(max_possible_prime + "\n");
}
 
// Driver Code
public static void main(String[] args)
{
    int n = 4;
     
    // Function Call
    findMaxPrimeDivisor(n);
}
}
 
// This code is contributed by amal kumar choubey

# Python3 implementation to find the
# maximum possible prime divisor
# of a number can have N divisors
 
# Function to find the maximum
# possible prime divisors of a
# number can have with N divisors
def findMaxPrimeDivisor(n):
     
    max_possible_prime = 0
     
    # Number of time number
    # divided by 2
    while (n % 2 == 0):
        max_possible_prime += 1
        n = n // 2
         
    # Divide by other prime numbers
    i = 3
    while(i * i <= n):
        while (n % i == 0):
             
            max_possible_prime += 1
            n = n // i
        i = i + 2
         
    # If the last number of also
    # prime then also include it
    if (n > 2):
        max_possible_prime += 1
     
    print(max_possible_prime)
 
# Driver Code
n = 4
 
# Function Call
findMaxPrimeDivisor(n)
 
# This code is contributed by SHUBHAMSINGH10

// C# implementation to find the
// maximum possible prime divisor
// of a number can have N divisors
using System;
 
class GFG{
 
// Function to find the
// maximum possible prime divisors
// of a number can have with N divisors
static void findMaxPrimeDivisor(int n)
{
    int max_possible_prime = 0;
 
    // Number of time number
    // divided by 2
    while (n % 2 == 0)
    {
        max_possible_prime++;
        n = n / 2;
    }
 
    // Divide by other prime numbers
    for(int i = 3; i * i <= n; i = i + 2)
    {
       while (n % i == 0)
       {
           max_possible_prime++;
           n = n / i;
       }
    }
 
    // If the last number of also
    // prime then also include it
    if (n > 2)
    {
        max_possible_prime++;
    }
    Console.Write(max_possible_prime + "\n");
}
 
// Driver Code
public static void Main(String[] args)
{
    int n = 4;
     
    // Function Call
    findMaxPrimeDivisor(n);
}
}
 
// This code is contributed by amal kumar choubey

<script>
 
// JavaScript implementation to find the
// maximum possible prime divisor
// of a number can have N divisors
 
// Function to find the maximum
// possible prime divisors of a
// number can have with N divisors
function findMaxPrimeDivisor(n)
{
    let max_possible_prime = 0;
 
    // Number of time number
    // divided by 2
    while (n % 2 == 0)
    {
        max_possible_prime++;
        n = Math.floor(n / 2);
    }
 
    // Divide by other prime numbers
    for(let i = 3; i * i <= n; i = i + 2)
    {
        while (n % i == 0)
        {
            max_possible_prime++;
            n = Math.floor(n / i);
        }
    }
 
    // If the last number of also
    // prime then also include it
    if (n > 2)
    {
        max_possible_prime++;
    }
    document.write(max_possible_prime + "\n");
}
 
// Driver Code
let n = 4;
 
// Function Call
findMaxPrimeDivisor(n);
 
// This code is contributed by Surbhi Tyagi.
 
</script>

2

Complejidad de tiempo: O(sqrt(N) * logN )

Espacio Auxiliar: O(1)