Encuentra el número más pequeño que divide a X^X

Dado un número X , encuentra el número más pequeño, que es mayor que 1 , que divide a X ^X. En la pregunta dada, siempre se supone que X es mayor que 1.
Ejemplos: 
 

Entrada: X = 6 
Salida: 2 
Explicación: Como, 6 ⁶ es igual a 46656, que es divisible por 2 y es el más pequeño entre todos sus divisores. 
Entrada: X = 3 
Salida: 3 
Explicación: Como, 3 ³ es igual a 27, que es divisible por 3 y es el más pequeño entre todos sus divisores. 
 

Enfoque: 
La observación principal de este problema es que si un número P divide a X , entonces también divide a X ^X , por lo que no necesitamos calcular el valor de X ^X. Lo que tenemos que hacer es encontrar el número más pequeño que divide a X, que siempre será un número primo.
A continuación se muestra la implementación del enfoque anterior:
 

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the required smallest number
int SmallestDiv(int n)
{
  
    for (int i = 2; i * i <= n; i++) {
        // Finding smallest number that divides n
        if (n % i == 0) {
 
            // i divides n and return this
            // value immediately
            return i;
        }
    }
  
    // If n is a prime number then answer should be n,
    // As we can't take 1 as our answer.
    return n;
}
  
// Driver Code
int main()
{
  
    int X = 385;
  
    int ans = SmallestDiv(X);
    cout << ans << "\n";
  
    return 0;
}

// Java implementation of above approach
class GFG{
 
// Function to find the
// required smallest number
static int SmallestDiv(int n)
{
    for(int i = 2; i * i <= n; i++)
    {
         
       // Finding smallest number
       // that divides n
       if (n % i == 0)
       {
 
           // i divides n and return this
           // value immediately
           return i;
       }
    }
 
    // If n is a prime number then
    // answer should be n, as we
    // can't take 1 as our answer.
    return n;
}
 
// Driver Code
public static void main(String[] args)
{
    int X = 385;
    int ans = SmallestDiv(X);
     
    System.out.print(ans + "\n");
}
}
 
// This code is contributed by gauravrajput1

# Python3 implementation of above approach
 
# Function to find the required smallest number
def SmallestDiv(n):
   
    i = 2
    while i * i <= n:
 
        # Finding smallest number that divides n
        if (n % i == 0):
  
            # i divides n and return this
            # value immediately
            return i
        i += 1
     
    # If n is a prime number then answer should be n,
    # As we can't take 1 as our answer.
    return n
   
# Driver Code
if __name__=="__main__":
 
    X = 385
    ans = SmallestDiv(X)
 
    print(ans)
 
# This code is contributed by Yash_R

// C# implementation of above approach
using System;
 
class GFG {
     
// Function to find the
// required smallest number
static int SmallestDiv(int n)
{
    for(int i = 2; i * i <= n; i++)
    {
         
       // Finding smallest number
       // that divides n
       if (n % i == 0)
       {
            
           // i divides n and return this
           // value immediately
           return i;
       }
    }
 
    // If n is a prime number then
    // answer should be n, as we
    // can't take 1 as our answer.
    return n;
}
 
// Driver code
public static void Main(String[] args)
{
    int X = 385;
    int ans = SmallestDiv(X);
     
    Console.Write(ans + "\n");
}
}
 
// This code is contributed by shivanisinghss2110

<script>
 
    // Javascript implementation of above approach
     
    // Function to find the required smallest number
    function SmallestDiv(n)
    {
 
        for (let i = 2; i * i <= n; i++) {
            // Finding smallest number that divides n
            if (n % i == 0) {
 
                // i divides n and return this
                // value immediately
                return i;
            }
        }
 
        // If n is a prime number then answer should be n,
        // As we can't take 1 as our answer.
        return n;
    }
 
    let X = 385;
    
    let ans = SmallestDiv(X);
    document.write(ans + "</br>");
 
</script>

Output: 5

Complejidad del tiempo: O(sqrt(X))