Encuentra el mayor número bueno en los divisores del número dado N

Dado un número N. La tarea es encontrar el mayor número bueno entre los divisores de un número dado N. Un número X se define como el número bueno si no existe un entero positivo a > 1, tal que a^2 sea un divisor de x

Ejemplos: 

Input: N = 10
Output: 10
In 1, 2, 5, 10. 
10 is the largest good number

Input: N = 12
Output: 6
In 1, 2, 3, 4, 6, 12. 
6 is the largest good number 

Enfoque: Encuentre todos los divisores primos de N. Suponga que son p1, p2, …, pk (en O(sqrt(n)) complejidad temporal). Si la respuesta es a, entonces sabemos que para cada 1 <= I <= k, obviamente, a no es divisible por pi^2 (y todas las potencias mayores de pi). Entonces a <= p1 × p2 ×… × pk. Y sabemos que p1 × p2 × … × pk es en sí mismo un buen número. Entonces, la respuesta es p1 × p2 ×…× pk.

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

// CPP program to find the largest, good
// number in the divisors of given number N.
#include <bits/stdc++.h>
using namespace std;
 
// function to return distinct prime factors
vector<int> PrimeFactors(int n)
{
    // to store distinct prime factors
    vector<int> v;
 
    int x = n;
 
    // run a loop upto sqrt(n)
    for (int i = 2; i * i <= n; i++) {
        if (x % i == 0) {
 
            // place this prime factor in vector
            v.push_back(i);
            while (x % i == 0)
                x /= i;
        }
    }
 
    // This condition is to handle the case when n
    // is a prime number greater than 1
    if (x > 1)
        v.push_back(x);
 
    return v;
}
 
// function that returns good number
int GoodNumber(int n)
{
    // distinct prime factors
    vector<int> v = PrimeFactors(n);
 
    // to store answer
    int ans = 1;
 
    // product of all distinct prime
    // factors is required answer
    for (int i = 0; i < v.size(); i++)
        ans *= v[i];
 
    return ans;
}
 
// Driver code
int main()
{
    int n = 12;
 
    // function call
    cout << GoodNumber(n);
 
    return 0;
}

// Java program to find the largest, good
// number in the divisors of given number N.
 
import java.util.*;
 
class GFG {
    // function to return distinct prime factors
 
    static Vector<Integer> PrimeFactors(int n)
    {
 
        // to store distinct prime factors
        Vector<Integer> v = new Vector<Integer>();
        int x = n;
 
        // run a loop upto sqrt(n)
        for (int i = 2; i * i <= n; i++) {
            if (x % i == 0) {
 
                // place this prime factor in vector
                v.add(i);
                while (x % i == 0)
                    x /= i;
            }
        }
 
        // This condition is to handle the case when n
        // is a prime number greater than 1
        if (x > 1)
            v.add(x);
 
        return v;
    }
 
    // function that returns good number
    static int GoodNumber(int n)
    {
        // distinct prime factors
        Vector<Integer> v = new Vector<Integer>(PrimeFactors(n));
 
        // to store answer
        int ans = 1;
 
        // product of all distinct prime
        // factors is required answer
        for (int i = 0; i < v.size(); i++)
            ans *= v.get(i);
 
        return ans;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int n = 12;
 
        // function call
        System.out.println(GoodNumber(n));
    }
}
 
// This code is contributed by ihritik

# Python 3 program to find the
# largest, good number in the
# divisors of given number N.
 
# function to return distinct
# prime factors
def PrimeFactors(n):
 
    # to store distinct
    # prime factors
    v = []
 
    x = n
 
    # run a loop upto sqrt(n)
    i = 2
    while(i * i <= n):
        if (x % i == 0) :
 
            # place this prime factor
            # in vector
            v.append(i)
            while (x % i == 0):
                x //= i
                 
        i += 1
 
    # This condition is to handle
    # the case when n is a prime
    # number greater than 1
    if (x > 1):
        v.append(x)
 
    return v
 
# function that returns good number
def GoodNumber(n):
     
    # distinct prime factors
    v = PrimeFactors(n)
 
    # to store answer
    ans = 1
 
    # product of all distinct prime
    # factors is required answer
    for i in range(len(v)):
        ans *= v[i]
 
    return ans
 
# Driver code
if __name__ == "__main__":
    n = 12
 
    # function call
    print(GoodNumber(n))
 
# This code is contributed
# by ChitraNayal

// C# program to find the largest, good
// number in the divisors of given number N.
using System;
using System.Collections.Generic;
public class GFG {
    // function to return distinct prime factors
 
    static List<int> PrimeFactors(int n)
    {
 
        // to store distinct prime factors
        List<int> v = new List<int>();
        int x = n;
 
        // run a loop upto sqrt(n)
        for (int i = 2; i * i <= n; i++) {
            if (x % i == 0) {
 
                // place this prime factor in vector
                v.Add(i);
                while (x % i == 0)
                    x /= i;
            }
        }
 
        // This condition is to handle the case when n
        // is a prime number greater than 1
        if (x > 1)
            v.Add(x);
 
        return v;
    }
 
    // function that returns good number
    static int GoodNumber(int n)
    {
        // distinct prime factors
        List<int> v = new List<int>(PrimeFactors(n));
 
        // to store answer
        int ans = 1;
 
        // product of all distinct prime
        // factors is required answer
        for (int i = 0; i < v.Count; i++)
            ans *= v[i];
 
        return ans;
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int n = 12;
 
        // function call
        Console.WriteLine(GoodNumber(n));
    }
}
 
// This code has been contributed by 29AjayKumar

<?php
// PHP program to find the largest, good
// number in the divisors of given number N.
 
// function to return distinct prime factors
function PrimeFactors($n)
{
    // to store distinct prime factors
    $v = array();
 
    $x = $n;
 
    // run a loop upto sqrt(n)
    for ($i = 2; $i * $i <= $n; $i++)
    {
        if ($x % $i == 0)
        {
 
            // place this prime factor in vector
            array_push($v, $i);
            while ($x % $i == 0)
                $x /= $i;
        }
    }
 
    // This condition is to handle the case when n
    // is a prime number greater than 1
    if ($x > 1)
        array_push($v, $x);
 
    return $v;
}
 
// function that returns good number
function GoodNumber($n)
{
    // distinct prime factors
    $v = PrimeFactors($n);
 
    // to store answer
    $ans = 1;
 
    // product of all distinct prime
    // factors is required answer
    for ($i = 0; $i < count($v); $i++)
        $ans *= $v[$i];
 
    return $ans;
}
 
// Driver code
$n = 12;
 
// function call
echo GoodNumber($n);
 
// This code is contributed by Rajput-Ji
?>

<script>
// Javascript program to find the largest, good
// number in the divisors of given number N.
     
    // function to return distinct prime factors
    function PrimeFactors(n)
    {
        // to store distinct prime factors
        let v = [];
        let x = n;
   
        // run a loop upto sqrt(n)
        for (let i = 2; i * i <= n; i++) {
            if (x % i == 0) {
   
                // place this prime factor in vector
                v.push(i);
                while (x % i == 0)
                    x = Math.floor(x/i);
            }
        }
   
        // This condition is to handle the case when n
        // is a prime number greater than 1
        if (x > 1)
            v.push(x);
   
        return v;
    }
     
    // function that returns good number
    function GoodNumber(n)
    {
        // distinct prime factors
        let v = PrimeFactors(n);
   
        // to store answer
        let ans = 1;
   
        // product of all distinct prime
        // factors is required answer
        for (let i = 0; i < v.length; i++)
            ans *= v[i];
   
        return ans;
    }
     
    // Driver code
    let n = 12;
 
    // function call
    document.write(GoodNumber(n));
 
 
// This code is contributed by rag2127
</script>

6

Complejidad del tiempo: O(sqrt(n) + k), donde n es el número dado yk es el número de factores primos distintos.

Complejidad espacial: O(k), para almacenar distintos factores primos.