Mayor divisor de un número no divisible por un cuadrado perfecto

Dado un entero positivo, N . Encuentra el divisor más grande del número dado que no es divisible por un cuadrado perfecto mayor que 1.

Ejemplos: 

Input : 12
Output : 6
Explanation : Divisors of 12 are 1, 2, 3, 4, 6 and 12. 
Since 12 is divisible by 4 (a perfect square), 
it can't be required divisor. 6 is not divisible 
by any perfect square.
 
Input :97
Output :97

Un enfoque simple es encontrar todos los divisores del número N dado al iterar hasta la raíz cuadrada de N y mantenerlos en orden (Descendente) en una lista. Aquí los estamos insertando en un conjunto en orden descendente para mantenerlos ordenados. Además, haz una lista de todos los cuadrados perfectos hasta 10 ¹⁰ iterando de 1 a 10 ⁵ . 
Ahora, para cada divisor a partir del mayor, comprueba si es divisible por algún cuadrado perfecto de la lista o no. Si un divisor no es divisible por ningún perfecto, simplemente devuélvelo como la respuesta.

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

// C++ Program to find the largest
// divisor not divisible by any
// perfect square greater than 1
#include <bits/stdc++.h>
using namespace std;
 
const int MAX = 1e5;
 
// Function to find the largest
// divisor not divisible by any
// perfect square greater than 1
int findLargestDivisor(int n)
{
    // set to store divisors in
    // descending order
    int m = n;
    set<int, greater<int> > s;
    s.insert(1);
    s.insert(n);
 
    for (int i = 2; i < sqrt(n) + 1; i++) {
        // If the number is divisible
        // by i, then insert it
        if (n % i == 0) {
            s.insert(n / i);
            s.insert(i);
            while (m % i == 0)
                m /= i;
        }
    }
 
    if (m > 1)
        s.insert(m);
 
    // Vector to store perfect squares
    vector<int> vec;
    for (int i = 2; i <= MAX; i++)
        vec.push_back(i * i);
 
    // Check for each divisor, if it is not
    // divisible by any perfect square,
    // simply return it as the answer.
    for (auto d : s) {
        int divi = 0;
        for (int j = 0; j < vec.size()
                        && vec[j] <= d;
             j++) {
            if (d % vec[j] == 0) {
                divi = 1;
                break;
            }
        }
        if (!divi)
            return d;
    }
}
 
// Driver Code
int main()
{
    int n = 12;
    cout << findLargestDivisor(n) << endl;
 
    n = 97;
    cout << findLargestDivisor(n) << endl;
    return 0;
}

// Java Program to find the largest
// divisor not divisible by any
// perfect square greater than 1
import java.util.*;
class Main{
     
static int MAX = (int)1e5;
     
// Function to find the largest
// divisor not divisible by any
// perfect square greater than 1
public static int findLargestDivisor(int n)
{
  // set to store divisors in
  // descending order
  int m = n;
  Set<Integer> s =
      new HashSet<Integer>();
  s.add(1);
  s.add(n);
 
  for (int i = 2;
           i < (int)Math.sqrt(n) + 1; i++)
  {
    // If the number is divisible
    // by i, then insert it
    if (n % i == 0)
    {
      s.add(n / i);
      s.add(i);
      while (m % i == 0)
        m /= i;
    }
  }
 
  if (m > 1)
    s.add(m);
 
  List<Integer> l =
       new ArrayList<Integer>(s);
 
  Collections.sort(l);
  Collections.reverse(l);
 
  // Vector to store
  // perfect squares
  Vector<Integer> vec =
         new Vector<Integer>();
 
  for (int i = 2; i <= MAX; i++)
    vec.add(i * i);
 
  // Check for each divisor, if
  // it is not divisible by any
  // perfect square, simply return
  // it as the answer.
  for (int d : l)
  {
    int divi = 0;
     
    for (int j = 0;
             j < vec.size() &&
             vec.get(j) <= d; j++)
    {
      if (d % vec.get(j) == 0)
      {
        divi = 1;
        break;
      }
    }
    if (divi == 0)
      return d;
  }
  return 0;
}
 
// Driver code   
public static void main(String[] args)
{
  int n = 12;
  System.out.println(findLargestDivisor(n));
 
  n = 97;
  System.out.println(findLargestDivisor(n));
}
}
 
// This code is contributed by divyeshrabadiya07

# Python3 Program to find the largest
# divisor not divisible by any
# perfect square greater than 1
 
MAX = 10 ** 5
 
# Function to find the largest
# divisor not divisible by any
# perfect square greater than 1
def findLargestDivisor(n):
 
    # set to store divisors in
    # descending order
    m = n
    s = set()
    s.add(1)
    s.add(n)
 
    for i in range(2, int(n ** (0.5)) + 1):
         
        # If the number is divisible
        # by i, then insert it
        if n % i == 0:
            s.add(n // i)
            s.add(i)
            while m % i == 0:
                m //= i
         
    if m > 1:
        s.add(m)
 
    # Vector to store perfect squares
    vec = [i**2 for i in range(2, MAX + 1)]
 
    # Check for each divisor, if it is not
    # divisible by any perfect square,
    # simply return it as the answer.
    for d in sorted(s, reverse = True):
         
        divi, j = 0, 0
        while j < len(vec) and vec[j] <= d:
 
            if d % vec[j] == 0:
                divi = 1
                break
            j += 1       
         
        if not divi:
            return d
 
# Driver Code
if __name__ == "__main__":
 
    n = 12
    print(findLargestDivisor(n))
 
    n = 97
    print(findLargestDivisor(n))
     
# This code is contributed by Rituraj Jain

// C# program to find the largest
// divisor not divisible by any
// perfect square greater than 1
using System;
using System.Collections.Generic;
 
class GFG{
     
static int MAX = (int)1e5;
 
// Function to find the largest
// divisor not divisible by any
// perfect square greater than 1
static int findLargestDivisor(int n)
{
     
    // Set to store divisors in
    // descending order
    int m = n;
     
    HashSet<int> s = new HashSet<int>();
    s.Add(1);
    s.Add(n);
     
    for(int i = 2;
            i < (int)Math.Sqrt(n) + 1;
            i++)
    {
         
        // If the number is divisible
        // by i, then insert it
        if (n % i == 0)
        {
            s.Add(n / i);
            s.Add(i);
             
            while (m % i == 0)
                m /= i;
        }
    }
     
    if (m > 1)
        s.Add(m);
     
    List<int> l = new List<int>(s);
    l.Sort();
    l.Reverse();
     
    // Vector to store
    // perfect squares
    List<int> vec = new List<int>();
     
    for(int i = 2; i <= MAX; i++)
        vec.Add(i * i);
     
    // Check for each divisor, if
    // it is not divisible by any
    // perfect square, simply return
    // it as the answer.
    foreach(int d in l)
    {
        int divi = 0;
         
        for(int j = 0;
                j < vec.Count && vec[j] <= d;
                j++)
        {
            if (d % vec[j] == 0)
            {
                divi = 1;
                break;
            }
        }
        if (divi == 0)
            return d;
    }
    return 0;
} 
 
// Driver code
static void Main()
{
    int n = 12;
    Console.WriteLine(findLargestDivisor(n));
     
    n = 97;
    Console.WriteLine(findLargestDivisor(n));
}
}
 
// This code is contributed by divyesh072019

<script>
// Javascript Program to find the largest
// divisor not divisible by any
// perfect square greater than 1
 
let MAX = 100000;
 
// Function to find the largest
// divisor not divisible by any
// perfect square greater than 1
function findLargestDivisor(n)
{
  // set to store divisors in
  // descending order
  let m = n;
  let s = new Set();
  s.add(1);
  s.add(n);
  
  for (let i = 2;
           i < Math.floor(Math.sqrt(n)) + 1; i++)
  {
    // If the number is divisible
    // by i, then insert it
    if (n % i == 0)
    {
      s.add(Math.floor(n / i));
      s.add(i);
      while (m % i == 0)
        m = Math.floor(m/i);
    }
  }
  
  if (m > 1)
    s.add(m);
  
  let l =Array.from(s);
  
  l.sort(function(a,b){return a-b;});
  l.reverse();
  // Vector to store
  // perfect squares
  let vec = [];
  
  for (let i = 2; i <= MAX; i++)
    vec.push(i * i);
  
  // Check for each divisor, if
  // it is not divisible by any
  // perfect square, simply return
  // it as the answer.
  for (let d=0;d<l.length;d++)
  {
    let divi = 0;
      
    for (let j = 0;
             j < vec.length &&
             vec[j] <= l[d]; j++)
    {
      if (l[d] % vec[j] == 0)
      {
        divi = 1;
        break;
      }
    }
    if (divi == 0)
      return l[d];
  }
  return 0;
}
 
// Driver code  
let n = 12;
document.write(findLargestDivisor(n)+"<br>");
 
n = 97;
document.write(findLargestDivisor(n)+"<br>");
     
     
// This code is contributed by rag2127
</script>

6
97

Complejidad del tiempo: O(sqrt(n)*logn)

Espacio Auxiliar: O(n)

Un enfoque eficiente es dividir n por i para cada i tal que (i * i) divide a n. 

// Efficient C++ Program to find the
// largest divisor not divisible by any
// perfect square greater than 1
#include <bits/stdc++.h>
using namespace std;
  
// Function to find the largest
// divisor not divisible by any
// perfect square greater than 1
int findLargestDivisor(int n)
{
    for (int i = 2; i < sqrt(n) + 1; i++) {
         
        // If the number is divisible
        // by i*i, then remove one i
        while (n % (i * i) == 0) {
            n = n / i;
        }
    }
   
    // Now all squares are removed from n
    return n;   
}
  
// Driver Code
int main()
{
    int n = 12;
    cout << findLargestDivisor(n) << endl;
  
    n = 97;
    cout << findLargestDivisor(n) << endl;
    return 0;
}

// Efficient Java Program to find the
// largest divisor not divisible by any
// perfect square greater than 1
 
public class GFG
{
 
    // Function to find the largest
    // divisor not divisible by any
    // perfect square greater than 1
    static int findLargestDivisor(int n)
    {
        for (int i = 2; i < Math.sqrt(n) + 1; i++) {
             
            // If the number is divisible
            // by i*i, then remove one i
            while (n % (i * i) == 0) {
                n = n / i;
            }
        }
         
        // Now all squares are removed from n
        return n;    
    }
     
    // Driver Code
    public static void main(String args[])
    {
        int n = 12;
        System.out.println(findLargestDivisor(n)) ;
     
        n = 97;
        System.out.println(findLargestDivisor(n)) ;
     
    }
    // This code is contributed
    // by Ryuga
}

# Efficient Python3 Program to find the
# largest divisor not divisible by any
# perfect square greater than 1
import math
 
# Function to find the largest
# divisor not divisible by any
# perfect square greater than 1
def findLargestDivisor( n):
 
    for i in range (2, int(math.sqrt(n)) + 1) :
         
        # If the number is divisible
        # by i*i, then remove one i
        while (n % (i * i) == 0) :
            n = n // i
     
    # Now all squares are removed from n
    return n
 
# Driver Code
if __name__ == "__main__":
 
    n = 12
    print (findLargestDivisor(n))
 
    n = 97
    print (findLargestDivisor(n))
 
# This code is contributed by ita_c

// Efficient C# Program to find the
// largest divisor not divisible by any
// perfect square greater than 1
using System;
public class GFG
{
 
    // Function to find the largest
    // divisor not divisible by any
    // perfect square greater than 1
    static int findLargestDivisor(int n)
    {
        for (int i = 2; i < Math.Sqrt(n) + 1; i++) {
             
            // If the number is divisible
            // by i*i, then remove one i
            while (n % (i * i) == 0) {
                n = n / i;
            }
        }
         
        // Now all squares are removed from n
        return n;    
    }
     
    // Driver Code
    public static void Main()
    {
        int n = 12;
        Console.WriteLine(findLargestDivisor(n)) ;
     
        n = 97;
        Console.WriteLine(findLargestDivisor(n)) ;
     
    }
}
    // This code is contributed
    // by Mukul Singh

<?php
// Efficient PHP Program to find the
// largest divisor not divisible by
// any perfect square greater than 1
 
// Function to find the largest
// divisor not divisible by any
// perfect square greater than 1
function findLargestDivisor($n)
{
    for ($i = 2; $i < sqrt($n) + 1; $i++)
    {
         
        // If the number is divisible
        // by i*i, then remove one i
        while ($n % ($i * $i) == 0)
        {
            $n = $n / $i;
        }
    }
 
    // Now all squares are removed from n
    return $n;
}
 
// Driver Code
$n = 12;
echo(findLargestDivisor($n));
echo("\n");
 
$n = 97;
echo(findLargestDivisor($n)) ;
 
// This code is contributed
// by Shivi_Aggarwal
?>

<script>
    // Efficient Javascript Program to find the
    // largest divisor not divisible by any
    // perfect square greater than 1
     
    // Function to find the largest
    // divisor not divisible by any
    // perfect square greater than 1
    function findLargestDivisor(n)
    {
        for (let i = 2; i < Math.sqrt(n) + 1; i++)
        {
 
            // If the number is divisible
            // by i*i, then remove one i
            while (n % (i * i) == 0) {
                n = n / i;
            }
        }
 
        // Now all squares are removed from n
        return n;  
    }
     
    let n = 12;
    document.write(findLargestDivisor(n) + "</br>");
   
    n = 97;
    document.write(findLargestDivisor(n) + "</br>");
     
    // This code is contributed by suresh07.
</script>

6
97

Complejidad del tiempo: O(sqrt(n))

Espacio Auxiliar: O(1)