Mayor factor de un número dado que es un cuadrado perfecto

Dado un número  . La tarea es encontrar el factor más grande de ese número que es un cuadrado perfecto.
Ejemplos : 

Input : N = 420
Output : 4

Input : N = 100
Output : 100

Una solución simple es recorrer todos los números en orden decreciente desde el número dado hasta 1 y si alguno de estos números es un factor del número dado y también es un cuadrado perfecto, imprime ese número.
Complejidad del tiempo : O(N)
Mejor solución: una mejor solución es usar la descomposición en factores primos del número dado.

• Primero encuentra todos los factores primos de ese número hasta sqrt(num).
• Tome una variable, responda e inicialícela a 1. Representa el número cuadrado más grande que también es un factor de ese número.
• Ahora, verifique si cualquier número primo ocurre un número par de veces en la factorización prima del número dado, si es así, entonces multiplique la respuesta con ese factor primo el número de veces que ocurre.
• De lo contrario, si ocurre un número impar de veces, multiplique la respuesta con el número primo (K – 1) veces, K es la frecuencia de ese factor primo en la descomposición en factores primos.

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

// C++ program to find the largest factor of
// a number which is also a perfect square
 
#include <cmath>
#include <iostream>
using namespace std;
 
// Function to find the largest factor
// of a given number which
// is a perfect square
int largestSquareFactor(int num)
{
    // Initialise the answer to 1
    int answer = 1;
 
    // Finding the prime factors till sqrt(num)
    for (int i = 2; i < sqrt(num); ++i) {
        // Frequency of the prime factor in the
        // factorisation initialised to 0
        int cnt = 0;
        int j = i;
 
        while (num % j == 0) {
            cnt++;
            j *= i;
        }
 
        // If the frequency is odd then multiply i
        // frequency-1 times to the answer
        if (cnt & 1) {
            cnt--;
            answer *= pow(i, cnt);
        }
        // Else if it is even, multiply
        // it frequency times
        else {
            answer *= pow(i, cnt);
        }
    }
 
    return answer;
}
 
// Driver Code
int main()
{
    int N = 420;
 
    cout << largestSquareFactor(N);
 
    return 0;
}

// Java program to find the largest factor of
// a number which is also a perfect square
 
class GFG
{
   
// Function to find the largest factor
// of a given number which
// is a perfect square
static int largestSquareFactor(int num)
{
    // Initialise the answer to 1
    int answer = 1;
   
    // Finding the prime factors till sqrt(num)
    for (int i = 2; i < Math.sqrt(num); ++i) {
        // Frequency of the prime factor in the
        // factorisation initialised to 0
        int cnt = 0;
        int j = i;
   
        while (num % j == 0) {
            cnt++;
            j *= i;
        }
   
        // If the frequency is odd then multiply i
        // frequency-1 times to the answer
        if ((cnt & 1)!=0) {
            cnt--;
            answer *= Math.pow(i, cnt);
        }
        // Else if it is even, multiply
        // it frequency times
        else {
            answer *= Math.pow(i, cnt);
        }
    }
   
    return answer;
}
   
// Driver Code
public static void  main(String args[])
{
    int N = 420;
   
    System.out.println(largestSquareFactor(N));
   
}
}

# Python 3 program to find the largest
# factor of a number which is also a
# perfect square
import math
 
# Function to find the largest factor
# of a given number which is a
# perfect square
def largestSquareFactor( num):
 
    # Initialise the answer to 1
    answer = 1
 
    # Finding the prime factors till sqrt(num)
    for i in range(2, int(math.sqrt(num))) :
         
        # Frequency of the prime factor in the
        # factorisation initialised to 0
        cnt = 0
        j = i
 
        while (num % j == 0) :
            cnt += 1
            j *= i
 
        # If the frequency is odd then multiply i
        # frequency-1 times to the answer
        if (cnt & 1) :
            cnt -= 1
            answer *= pow(i, cnt)
         
        # Else if it is even, multiply
        # it frequency times
        else :
            answer *= pow(i, cnt)
    return answer
 
# Driver Code
if __name__ == "__main__":
    N = 420
 
    print(largestSquareFactor(N))
 
# This code is contributed
# by ChitraNayal

// C# program to find the largest factor of
// a number which is also a perfect square
using System;
 
class GFG
{
     
// Function to find the largest factor of
// a given number which is a perfect square
static double largestSquareFactor(double num)
{
    // Initialise the answer to 1
    double answer = 1;
 
    // Finding the prime factors
    // till sqrt(num)
    for (int i = 2; i < Math.Sqrt(num); ++i)
    {
        // Frequency of the prime factor in
        // the factorisation initialised to 0
        int cnt = 0;
        int j = i;
 
        while (num % j == 0)
        {
            cnt++;
            j *= i;
        }
 
        // If the frequency is odd then multiply i
        // frequency-1 times to the answer
        if ((cnt & 1) != 0)
        {
            cnt--;
            answer *= Math.Pow(i, cnt);
        }
         
        // Else if it is even, multiply
        // it frequency times
        else
        {
            answer *= Math.Pow(i, cnt);
        }
    }
 
    return answer;
}
 
// Driver Code
static public void Main ()
{
    int N = 420;
    Console.WriteLine(largestSquareFactor(N));
}
}
 
// This code is contributed by Sach_Code

<?php
// PHP program to find the largest
// factor of a number which is also
// a perfect square
 
// Function to find the largest
// factor of a given number which
// is a perfect square
function largestSquareFactor($num)
{
    // Initialise the answer to 1
    $answer = 1;
 
    // Finding the prime factors
    // till sqrt(num)
    for ($i = 2; $i < sqrt($num); ++$i)
    {
        // Frequency of the prime factor
        // in the factorisation initialised to 0
        $cnt = 0;
        $j = $i;
 
        while ($num % $j == 0)
        {
            $cnt++;
            $j *= $i;
        }
 
        // If the frequency is odd then
        // multiply i frequency-1 times
        // to the answer
        if ($cnt & 1)
        {
            $cnt--;
            $answer *= pow($i, $cnt);
        }
         
        // Else if it is even, multiply
        // it frequency times
        else
        {
            $answer *= pow($i, $cnt);
        }
    }
 
    return $answer;
}
 
// Driver Code
$N = 420;
echo largestSquareFactor($N);
 
// This code is contributed
// by Sach_Code
?>

<script>
// Javascript program to find the largest factor of
// a number which is also a perfect square
 
// Function to find the largest factor
// of a given number which
// is a perfect square
function largestSquareFactor(num)
{
 
    // Initialise the answer to 1
    let answer = 1;
 
    // Finding the prime factors till sqrt(num)
    for (let i = 2; i < Math.sqrt(num); ++i)
    {
     
        // Frequency of the prime factor in the
        // factorisation initialised to 0
        let cnt = 0;
        let j = i;
 
        while (num % j == 0) {
            cnt++;
            j *= i;
        }
 
        // If the frequency is odd then multiply i
        // frequency-1 times to the answer
        if (cnt & 1)
        {
            cnt--;
            answer *= Math.pow(i, cnt);
        }
         
        // Else if it is even, multiply
        // it frequency times
        else {
            answer *= Math.pow(i, cnt);
        }
    }
 
    return answer;
}
 
// Driver Code
let N = 420;
 
document.write(largestSquareFactor(N));
 
// This code is contributed by souravmahato348.
</script>

4

Complejidad de tiempo : O( sqrt(N) )