Dado un número entero N. Encuentra el número mínimo de divisores libres cuadrados. En otras palabras, la factorización de N debe comprender solo aquellos divisores que no tengan cuadrados. Un número libre de cuadrados es aquel número que no es divisible por ningún cuadrado perfecto (por supuesto, 1 no será considerado como un cuadrado perfecto en este caso).
Restricciones: 2 ≤ N ≤ 10 6
Ejemplos:
Entrada: 24
Salida: 3
Explicación: 24 se representará como 24 = 6 x 2 x 2, aquí todos los factores
(6 y 2) están libres de cuadrados.
Nota: 24 no se puede representar como (24 = 12 x 2) o (24 = 24) o (24 = 8 x 3) porque en todas estas factorizaciones, cada factorización tiene al menos un número que no está libre de cuadrados, es decir, 12, 24 y 8 son divisibles por 4 (4 es un cuadrado perfecto). Por lo tanto, el número mínimo de divisores cuadrados libres es 3.
Entrada: 6
Salida: 1
Explicación: 6 se representará como 6 = 6, ya que 6 no es divisible por ningún cuadrado perfecto. Por lo tanto, el número mínimo de divisores cuadrados libres es 1.
Prerrequisitos: Criba de Eratóstenes
Un enfoque ingenuo es considerar todas las factorizaciones posibles del número N y luego comprobar si existe un número que no esté libre de cuadrados (divisible por algún cuadrado perfecto) para cada factorización. Si existe, descarte esa factorización, de lo contrario considere esa factorización en respuesta. Después de considerar todas las factorizaciones correctas, encuentre el número mínimo de divisores cuadrados libres.
Enfoque eficiente: construya Prime Sieve (usando el tamiz de Eratóstenes ) encontrando todos los factores primos hasta la raíz cuadrada de N (hasta 10 3teniendo en cuenta las limitaciones). Ahora, considere todos los factores primos menores o iguales a la raíz cuadrada de N y para cada factor primo encuentre su potencia máxima en el número N (como la potencia máxima de 2 en 24 es 3). Ahora, sabemos que si un factor primo tiene una potencia mayor que 1 en N, no se puede agrupar consigo mismo (por ejemplo, 2 tiene una potencia de 3 en 24, por lo tanto, 2 x 2 = 4 o 2 x 2 x 2 = 8 no puede ocurrir en la factorización de 24 ya que ninguno de ellos es libre de cuadrados) ya que será divisible por algún cuadrado perfecto. Pero un factor primo agrupado con otro factor primo (una sola vez) nunca será divisible por ningún cuadrado perfecto. Esto nos da la intuición de que la respuesta será el máximo de las potencias máximas de todos los factores primos en el número N. En otras palabras,
If prime factorization of N = f1p1 * f2p2 * ... * fnpn where f1, f2 ... fn are the prime factors and p1, p2 ... pn are their maximum respective powers in N. Then answer will be, ans = max(p1, p2, ..., pn) For e.g. 24 = 23 * 31 ans = max(3, 1) = 3
A continuación se muestra una ilustración para explicar el algoritmo anterior.
Sea N = 24 . La factorización de N se puede representar de muchas maneras y de ellas tenemos que encontrar aquella en la que haya divisores mínimos con cada divisor sin cuadrados. Algunas factorizaciones son:
24 = 24 (24 no es cuadrado libre)
24 = 2 * 12 (12 no es cuadrado libre)
24 = 3 * 8 (8 no es cuadrado libre)
24 = 4 * 6 (4 no es cuadrado libre)
24 = 6 * 2 * 2 (Cada divisor es cuadrado libre con número de divisores = 3)
24 = 3 * 2 * 2 * 2 (Cada divisor es cuadrado libre con número de divisores = 4)
Por lo tanto, la respuesta adecuada sería 3 (24 = 6 * 2 * 2). Ahora bien, si observamos detenidamente, no podemos agrupar un factor primo consigo mismo sino con otro factor primo. Como en este caso, 2 se agrupa con 3 para hacer 6 (cuadrado libre) para reducir la cantidad de divisores. Por lo tanto, la respuesta sería el máximo de las potencias máximas de todos los factores primos porque necesitamos al menos esa cantidad para mantener la condición de cuadrados libres y otros factores primos (cuya potencia no es máxima) se pueden agrupar con el factor primo con potencia máxima para minimizar el conteo de divisores.
A continuación se muestra la implementación del enfoque anterior. Aquí, haremos un preprocesamiento para encontrar factores primos (usando Sieve) para que podamos responder muchas consultas simultáneamente.
C++
// CPP Program to find the minimum
// number of square free divisors
#include <bits/stdc++.h>
using namespace std;
// Initializing MAX with SQRT(10 ^ 6)
#define MAX 1005
void SieveOfEratosthenes(vector<int>& primes)
{
// Create a boolean array "prime[0..n]" and initialize
// all entries it as true. A value in prime[i] will
// finally be false if i is Not a prime, else true.
bool prime[MAX];
memset(prime, true, sizeof(prime));
for (int p = 2; p * p < MAX; p++) {
// If prime[p] is not changed, then it is a prime
if (prime[p] == true) {
// Update all multiples of p
for (int i = p * 2; i < MAX; i += p)
prime[i] = false;
}
}
// Print all prime numbers
for (int p = 2; p < MAX; p++)
if (prime[p])
primes.push_back(p);
}
// This function returns the minimum number of
// Square Free divisors
int minimumSquareFreeDivisors(int N)
{
vector<int> primes;
// Precomputing Prime Factors
SieveOfEratosthenes(primes);
// holds max of max power of all prime factors
int max_count = 0;
for (int i = 0; i < primes.size() && primes[i] * primes[i] <= N; i++) {
if (N % primes[i] == 0) {
// holds the max power of current prime factor
int tmp = 0;
while (N % primes[i] == 0) {
tmp++;
N /= primes[i];
}
max_count = max(max_count, tmp);
}
}
// If number itself is prime, it will be included
// as answer and thus minimum required answer is 1
if (max_count == 0)
max_count = 1;
return max_count;
}
// Driver Code to test above functions
int main()
{
int N = 24;
cout << "Minimum Number of Square Free Divisors is "
<< minimumSquareFreeDivisors(N) << endl;
N = 6;
cout << "Minimum Number of Square Free Divisors is "
<< minimumSquareFreeDivisors(N) << endl;
return 0;
}
Java
// Java Program to find the minimum
// number of square free divisors
import java.util.Vector;
public class GFG {
// Initializing MAX with SQRT(10 ^ 6)
static final int MAX = 1005;
static void SieveOfEratosthenes(Vector<Integer> primes) {
// Create a boolean array "prime[0..n]" and initialize
// all entries it as true. A value in prime[i] will
// finally be false if i is Not a prime, else true.
boolean prime[] = new boolean[MAX];
for (int i = 0; i < prime.length; i++) {
prime[i] = true;
}
for (int p = 2; p * p < MAX; p++) {
// If prime[p] is not changed, then it is a prime
if (prime[p] == true) {
// Update all multiples of p
for (int i = p * 2; i < MAX; i += p) {
prime[i] = false;
}
}
}
// Print all prime numbers
for (int p = 2; p < MAX; p++) {
if (prime[p]) {
primes.add(primes.size(), p);
}
}
}
// This function returns the minimum number of
// Square Free divisors
static int minimumSquareFreeDivisors(int N) {
Vector<Integer> primes = new Vector<>();
// Precomputing Prime Factors
SieveOfEratosthenes(primes);
// holds max of max power of all prime factors
int max_count = 0;
for (int i = 0; i < primes.size() && primes.get(i) *
primes.get(i) <= N; i++) {
if (N % primes.get(i) == 0) {
// holds the max power of current prime factor
int tmp = 0;
while (N % primes.get(i) == 0) {
tmp++;
N /= primes.get(i);
}
max_count = Math.max(max_count, tmp);
}
}
// If number itself is prime, it will be included
// as answer and thus minimum required answer is 1
if (max_count == 0) {
max_count = 1;
}
return max_count;
}
// Driver Code to test above functions
public static void main(String[] args) {
int N = 24;
System.out.println("Minimum Number of Square Free Divisors is "
+ minimumSquareFreeDivisors(N));
N = 6;
System.out.println("Minimum Number of Square Free Divisors is "
+ minimumSquareFreeDivisors(N));
}
}
Python3
# Python 3 Program to find the minimum
# number of square free divisors
from math import sqrt
# Initializing MAX with SQRT(10 ^ 6)
MAX = 1005
def SieveOfEratosthenes(primes):
# Create a boolean array "prime[0..n]" and
# initialize all entries it as true. A value
# in prime[i] will finally be false if i is
# Not a prime, else true.
prime = [True for i in range(MAX)]
for p in range(2,int(sqrt(MAX)) + 1, 1):
# If prime[p] is not changed, then
# it is a prime
if (prime[p] == True):
# Update all multiples of p
for i in range(p * 2, MAX, p):
prime[i] = False
# Print all prime numbers
for p in range(2, MAX, 1):
if (prime[p]):
primes.append(p)
return primes
# This function returns the minimum number
# of Square Free divisors
def minimumSquareFreeDivisors(N):
prime = []
primes = []
# Precomputing Prime Factors
primes = SieveOfEratosthenes(prime)
# holds max of max power of all
# prime factors
max_count = 0
i = 0
while(len(primes) and primes[i] *
primes[i] <= N):
if (N % primes[i] == 0):
# holds the max power of current
# prime factor
tmp = 0
while (N % primes[i] == 0):
tmp += 1
N /= primes[i]
max_count = max(max_count, tmp)
i += 1
# If number itself is prime, it will be included
# as answer and thus minimum required answer is 1
if (max_count == 0):
max_count = 1
return max_count
# Driver Code
if __name__ == '__main__':
N = 24
print("Minimum Number of Square Free Divisors is",
minimumSquareFreeDivisors(N))
N = 6
print("Minimum Number of Square Free Divisors is",
minimumSquareFreeDivisors(N))
# This code is contributed by
# Surendra_Gangwar
C#
// C# Program to find the minimum
// number of square free divisors
using System;
using System.Collections.Generic;
public class GFG {
// Initializing MAX with SQRT(10 ^ 6)
static int MAX = 1005;
static void SieveOfEratosthenes(List<int> primes) {
// Create a boolean array "prime[0..n]" and initialize
// all entries it as true. A value in prime[i] will
// finally be false if i is Not a prime, else true.
bool []prime = new bool[MAX];
for (int i = 0; i < prime.Length; i++) {
prime[i] = true;
}
for (int p = 2; p * p < MAX; p++) {
// If prime[p] is not changed, then it is a prime
if (prime[p] == true) {
// Update all multiples of p
for (int i = p * 2; i < MAX; i += p) {
prime[i] = false;
}
}
}
// Print all prime numbers
for (int p = 2; p < MAX; p++) {
if (prime[p]) {
primes.Add(p);
}
}
}
// This function returns the minimum number of
// Square Free divisors
static int minimumSquareFreeDivisors(int N) {
List<int> primes = new List<int>();
// Precomputing Prime Factors
SieveOfEratosthenes(primes);
// holds max of max power of all prime factors
int max_count = 0;
for (int i = 0; i < primes.Count && primes[i] *
primes[i] <= N; i++) {
if (N % primes[i] == 0) {
// holds the max power of current prime factor
int tmp = 0;
while (N % primes[i] == 0) {
tmp++;
N /= primes[i];
}
max_count = Math.Max(max_count, tmp);
}
}
// If number itself is prime, it will be included
// as answer and thus minimum required answer is 1
if (max_count == 0) {
max_count = 1;
}
return max_count;
}
// Driver Code to test above functions
public static void Main(){
int N = 24;
Console.WriteLine("Minimum Number of Square Free Divisors is "
+ minimumSquareFreeDivisors(N));
N = 6;
Console.WriteLine("Minimum Number of Square Free Divisors is "
+ minimumSquareFreeDivisors(N));
}
// This code is contributed by Ryuga
}
Javascript
<script>
// Javascript Program to find the minimum
// number of square free divisors
// Initializing MAX with SQRT(10 ^ 6)
let MAX = 1005;
function SieveOfEratosthenes(primes) {
// Create a boolean array "prime[0..n]" and initialize
// all entries it as true. A value in prime[i] will
// finally be false if i is Not a prime, else true.
let prime = new Array(MAX);
for (let i = 0; i < prime.length; i++) {
prime[i] = true;
}
for (let p = 2; p * p < MAX; p++) {
// If prime[p] is not changed, then it is a prime
if (prime[p] == true) {
// Update all multiples of p
for (let i = p * 2; i < MAX; i += p) {
prime[i] = false;
}
}
}
// Print all prime numbers
for (let p = 2; p < MAX; p++) {
if (prime[p]) {
primes.push(p);
}
}
}
// This function returns the minimum number of
// Square Free divisors
function minimumSquareFreeDivisors(N) {
let primes = [];
// Precomputing Prime Factors
SieveOfEratosthenes(primes);
// holds max of max power of all prime factors
let max_count = 0;
for (let i = 0; i < primes.length && primes[i] *
primes[i] <= N; i++) {
if (N % primes[i] == 0) {
// holds the max power of current prime factor
let tmp = 0;
while (N % primes[i] == 0) {
tmp++;
N = parseInt(N / primes[i], 10);
}
max_count = Math.max(max_count, tmp);
}
}
// If number itself is prime, it will be included
// as answer and thus minimum required answer is 1
if (max_count == 0) {
max_count = 1;
}
return max_count;
}
let N = 24;
document.write("Minimum Number of Square Free Divisors is "
+ minimumSquareFreeDivisors(N) + "</br>");
N = 6;
document.write("Minimum Number of Square Free Divisors is "
+ minimumSquareFreeDivisors(N));
// This code is contributed by suresh07.
</script>
Producción:
Minimum Number of Square Free Divisors is 3 Minimum Number of Square Free Divisors is 1
Publicación traducida automáticamente
Artículo escrito por Nishant Tanwar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA