Dado un número entero N , la tarea es contar el número de divisores libres de cuadrados del número dado.
Se dice que un número no tiene cuadrados si ningún factor primo lo divide más de una vez, es decir, la mayor potencia de un factor primo que divide a N es uno.
Ejemplos:
Entrada: N = 72
Salida: 3
Explicación: 2, 3, 6 son los tres posibles números libres cuadrados que dividen 72.Entrada: N = 62290800
Salida: 31
Enfoque ingenuo:
para cada número entero N , encuentre sus factores y verifique si es un número sin cuadrados o no. Si se trata de un número sin cuadrados, aumente la cuenta o, de lo contrario, continúe con el siguiente número. Finalmente, imprime el conteo que nos da el número requerido de divisores de N sin cuadrados .
Complejidad temporal: O(N 3/2 )
Enfoque eficiente:
siga los pasos a continuación para resolver el problema:
- A partir de la definición de números sin cuadrados, se puede entender que al encontrar todos los factores primos del número dado N , se pueden encontrar todos los posibles números sin cuadrados que pueden dividir a N.
- Sea X el número de factores primos de N. Por lo tanto, 2 X – 1 números sin cuadrados se pueden formar usando estos factores primos de X.
- Dado que cada uno de estos X factores primos es un factor de N, cualquier combinación de productos de estos X factores primos también es un factor de N y, por lo tanto, habrá 2 X – 1 divisores cuadrados libres de N.
Ilustración:
- norte = 72
- Los factores primos de N son 2, 3.
- Por lo tanto, los tres posibles números libres cuadrados generados a partir de estos dos números primos son 2, 3 y 6.
- Por lo tanto, los divisores libres de cuadrados totales de 72 son 3( = 2 2 – 1).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to find the square
// free divisors of a given number
#include <bits/stdc++.h>
using namespace std;
// The function to check
// if a number is prime or not
bool IsPrime(int i)
{
// If the number is even
// then its not prime
if (i % 2 == 0 && i != 2)
return false;
else {
for (int j = 3;
j <= sqrt(i); j += 2) {
if (i % j == 0)
return false;
}
return true;
}
}
// Driver Code
int main()
{
// Stores the count of
// distinct prime factors
int c = 0;
int N = 72;
for (int i = 2;
i <= sqrt(N); i++) {
if (IsPrime(i)) {
if (N % i == 0) {
c++;
if (IsPrime(N / i)
&& i != (N / i)) {
c++;
}
}
}
}
// Print the number of
// square-free divisors
cout << pow(2, c) - 1
<< endl;
return 0;
}
Java
// Java program to find the square
// free divisors of a given number
import java.util.*;
class GFG{
// The function to check
// if a number is prime or not
static boolean IsPrime(int i)
{
// If the number is even
// then its not prime
if (i % 2 == 0 && i != 2)
return false;
else
{
for(int j = 3;
j <= Math.sqrt(i);
j += 2)
{
if (i % j == 0)
return false;
}
return true;
}
}
// Driver code
public static void main(String[] args)
{
// Stores the count of
// distinct prime factors
int c = 0;
int N = 72;
for(int i = 2;
i <= Math.sqrt(N); i++)
{
if (IsPrime(i))
{
if (N % i == 0)
{
c++;
if (IsPrime(N / i) &&
i != (N / i))
c++;
}
}
}
// Print the number of
// square-free divisors
System.out.print(Math.pow(2, c) - 1);
}
}
// This code is contributed by sanjoy_62
Python3
# Python3 program to find the square # free divisors of a given number import math # The function to check # if a number is prime or not def IsPrime(i): # If the number is even # then its not prime if (i % 2 == 0 and i != 2): return 0; else: for j in range(3, int(math.sqrt(i) + 1), 2): if (i % j == 0): return 0; return 1; # Driver code # Stores the count of # distinct prime factors c = 0; N = 72; for i in range(2, int(math.sqrt(N)) + 1): if (IsPrime(i)): if (N % i == 0): c = c + 1 if (IsPrime(N / i) and i != (N / i)): c = c + 1 # Print the number of # square-free divisors print (pow(2, c) - 1) # This code is contributed by sanjoy_62
C#
// C# program to find the square
// free divisors of a given number
using System;
class GFG{
// The function to check
// if a number is prime or not
static Boolean IsPrime(int i)
{
// If the number is even
// then its not prime
if (i % 2 == 0 && i != 2)
return false;
else
{
for(int j = 3;
j <= Math.Sqrt(i);
j += 2)
{
if (i % j == 0)
return false;
}
return true;
}
}
// Driver code
public static void Main(String[] args)
{
// Stores the count of
// distinct prime factors
int c = 0;
int N = 72;
for(int i = 2;
i <= Math.Sqrt(N); i++)
{
if (IsPrime(i))
{
if (N % i == 0)
{
c++;
if (IsPrime(N / i) &&
i != (N / i))
c++;
}
}
}
// Print the number of
// square-free divisors
Console.Write(Math.Pow(2, c) - 1);
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// Javascript program to find the square
// free divisors of a given number
// The function to check
// if a number is prime or not
function IsPrime(i)
{
// If the number is even
// then its not prime
if (i % 2 == 0 && i != 2)
return false;
else
{
for(j = 3; j <= Math.sqrt(i); j += 2)
{
if (i % j == 0)
return false;
}
return true;
}
}
// Driver code
// Stores the count of
// distinct prime factors
var c = 0;
var N = 72;
for(i = 2; i <= Math.sqrt(N); i++)
{
if (IsPrime(i))
{
if (N % i == 0)
{
c++;
if (IsPrime(N / i) &&
i != (N / i))
c++;
}
}
}
// Print the number of
// square-free divisors
document.write(Math.pow(2, c) - 1);
// This code is contributed by aashish1995
</script>
3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
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