Dado un entero positivo n . Encuentra el número mínimo que divide a n para que sea un cuadrado perfecto .
Ejemplos:
Input : n = 50 Output : 2 By Dividing n by 2, we get which is a perfect square. Input : n = 6 Output : 6 By Dividing n by 6, we get which is a perfect square. Input : n = 36 Output : 1
Un número es cuadrado perfecto si todos los factores primos aparecen un número par de veces. La idea es encontrar el factor primo de n y encontrar la potencia de cada factor primo. Ahora, encuentra y multiplica todos los factores primos cuya potencia es impar. La resultante de la multiplicación es la respuesta.
C++
// C++ program to find minimum number which divide n
// to make it a perfect square.
#include<bits/stdc++.h>
using namespace std;
// Return the minimum number to be divided to make
// n a perfect square.
int findMinNumber(int n)
{
int count = 0, ans = 1;
// Since 2 is only even prime, compute its
// power separately.
while (n%2 == 0)
{
count++;
n /= 2;
}
// If count is odd, it must be removed by dividing
// n by prime number.
if (count%2)
ans *= 2;
for (int i = 3; i <= sqrt(n); i += 2)
{
count = 0;
while (n%i == 0)
{
count++;
n /= i;
}
// If count is odd, it must be removed by
// dividing n by prime number.
if (count%2)
ans *= i;
}
if (n > 2)
ans *= n;
return ans;
}
// Driven Program
int main()
{
int n = 72;
cout << findMinNumber(n) << endl;
return 0;
}
Java
// Java program to find minimum number
// which divide n to make it a perfect square.
class GFG
{
// Return the minimum number to be
// divided to make n a perfect square.
static int findMinNumber(int n)
{
int count = 0, ans = 1;
// Since 2 is only even prime,
// compute its power separately.
while (n % 2 == 0)
{
count++;
n /= 2;
}
// If count is odd, it must be removed by dividing
// n by prime number.
if (count % 2 == 1)
ans *= 2;
for (int i = 3; i <= Math.sqrt(n); i += 2)
{
count = 0;
while (n % i == 0)
{
count++;
n /= i;
}
// If count is odd, it must be removed by
// dividing n by prime number.
if (count % 2 == 1)
ans *= i;
}
if (n > 2)
ans *= n;
return ans;
}
// Driver code
public static void main (String[] args)
{
int n = 72;
System.out.println(findMinNumber(n));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python program to find # minimum number which # divide n to make it a # perfect square. import math # Return the minimum # number to be divided # to make n a perfect # square. def findMinNumber(n): count = 0 ans = 1 # Since 2 is only # even prime, compute # its power separately. while n % 2 == 0: count += 1 n //= 2 # If count is odd, # it must be removed # by dividing n by # prime number. if count % 2 is not 0: ans *= 2 for i in range(3, (int)(math.sqrt(n)) + 1, 2): count = 0 while n % i == 0: count += 1 n //= i # If count is odd, it # must be removed by # dividing n by prime # number. if count % 2 is not 0: ans *= i if n > 2: ans *= n return ans # Driver Code n = 72 print(findMinNumber(n)) # This code is contributed # by Sanjit_Prasad.
C#
// C# program to find minimum
// number which divide n to
// make it a perfect square.
using System;
class GFG
{
// Return the minimum number
// to be divided to make
// n a perfect square.
static int findMinNumber(int n)
{
int count = 0, ans = 1;
// Since 2 is only even prime,
// compute its power separately.
while (n % 2 == 0)
{
count++;
n /= 2;
}
// If count is odd, it must
// be removed by dividing
// n by prime number.
if (count % 2 == 1)
ans *= 2;
for (int i = 3; i <= Math.Sqrt(n);
i += 2)
{
count = 0;
while (n % i == 0)
{
count++;
n /= i;
}
// If count is odd, it must
// be removed by dividing n
// by prime number.
if (count % 2 == 1)
ans *= i;
}
if (n > 2)
ans *= n;
return ans;
}
// Driver code
public static void Main ()
{
int n = 72;
Console.WriteLine(findMinNumber(n));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to find minimum
// number which divide n
// to make it a perfect square.
// Return the minimum number
// to be divided to make
// n a perfect square.
function findMinNumber($n)
{
$count = 0;
$ans = 1;
// Since 2 is only
// even prime,
// compute its
// power separately.
while ($n % 2 == 0)
{
$count++;
$n /= 2;
}
// If count is odd,
// it must be removed
// by dividing n by
// prime number.
if ($count % 2)
$ans *= 2;
for ($i = 3; $i <= sqrt($n); $i += 2)
{
$count = 0;
while ($n % $i == 0)
{
$count++;
$n /= $i;
}
// If count is odd,
// it must be removed
// by dividing n by
// prime number.
if ($count % 2)
$ans *= $i;
}
if ($n > 2)
$ans *= $n;
return $ans;
}
// Driver Code
$n = 72;
echo findMinNumber($n), "\n";
// This code is contributed by ajit.
?>
Javascript
<script>
// Javascript program to find minimum
// number which divide n
// to make it a perfect square.
// Return the minimum number
// to be divided to make
// n a perfect square.
function findMinNumber(n)
{
let count = 0;
let ans = 1;
// Since 2 is only
// even prime,
// compute its
// power separately.
while (n % 2 == 0)
{
count++;
n /= 2;
}
// If count is odd,
// it must be removed
// by dividing n by
// prime number.
if (count % 2)
ans *= 2;
for (let i = 3; i <= Math.sqrt(n); i += 2)
{
count = 0;
while (n % i == 0)
{
count++;
n /= i;
}
// If count is odd,
// it must be removed
// by dividing n by
// prime number.
if (count % 2)
ans *= i;
}
if (n > 2)
ans *= n;
return ans;
}
// Driver Code
let n = 72;
document.write(findMinNumber(n) + "\n");
// This code is contributed by _saurabh_jaiswal.
</script>
Producción:
2
Complejidad de Tiempo: O(√n log n)
Espacio Auxiliar: O(1)
Este artículo es una contribución de Aarti_Rathi y Anuj Chauhan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA