Factores cuadrados perfectos de un número

Dado un número entero N , la tarea es encontrar el número de factores de N que son un cuadrado perfecto .

Ejemplos:

Entrada: N = 100
Salida: 4
Explicación:
Hay cuatro factores de
100 (1, 4, 25, 100) que son cuadrados perfectos.
Entrada: N = 900
Salida: 8
Explicación:
Hay ocho factores de 900 (1, 4, 9, 25, 36, 100, 225, 900) que son cuadrados perfectos.

Enfoque ingenuo: el enfoque más simple para resolver este problema es encontrar todos los factores posibles del número N dado y, para cada factor, verificar si el factor es un cuadrado perfecto o no . Por cada factor que resulte ser así, aumente la cuenta . Imprime el conteo final .
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Enfoque eficiente:
Es necesario realizar las siguientes observaciones para optimizar el enfoque anterior:
El número de factores para un número viene dado por:

Factores de N = (1 + a ₁ )*(1 + a ₂ )*(1 + a ₃ )*..*(1 + a _n )
donde a ₁ , a ₂ , a ₃ , …, _an son los recuento de distintos factores primos de N.

En un cuadrado perfecto, la cuenta de factores primos distintos debe ser divisible por 2. Por lo tanto, la cuenta de factores que son un cuadrado perfecto está dada por:

Factores de N que son cuadrados perfectos = (1 + a _1/2 )*(1 + a ₂ /2)*…*(1 + a _n /2) donde a ₁ , a ₂ , a ₃ , …, a _n son el recuento de distintos factores primos de N.

Ilustración:

Los factores primos de N = 100 son 2, 2, 5, 5.
Por lo tanto, la cantidad de factores que son cuadrados perfectos son (1 + 2/2) * (1 + 2/2) = 4.
Los factores son 1, 4, 25, 100.

Por lo tanto, encuentra el conteo de factores primos y aplica la fórmula anterior para encontrar el conteo de factores que son un cuadrado perfecto.
A continuación se muestra la implementación del enfoque anterior:

C++

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns the count of
// factors that are perfect squares
int noOfFactors(int N)
{
    if (N == 1)
        return 1;
 
    // Stores the count of number
    // of times a prime number
    // divides N.
    int count = 0;
 
    // Stores the number of factors
    // that are perfect square
    int ans = 1;
 
    // Count number of 2's
    // that divides N
    while (N % 2 == 0) {
        count++;
        N = N / 2;
    }
 
    // Calculate ans according
    // to above formula
    ans *= (count / 2 + 1);
 
    // Check for all the possible
    // numbers that can divide it
    for (int i = 3;
         i * i <= N; i = i + 2) {
        count = 0;
 
        // Check the number of
        // times prime number
        // i divides it
        while (N % i == 0) {
            count++;
            N = N / i;
        }
 
        // Calculate ans according
        // to above formula
        ans *= (count / 2 + 1);
    }
 
    // Return final count
    return ans;
}
 
// Driver Code
int main()
{
    int N = 100;
 
    cout << noOfFactors(N);
 
    return 0;
}

Java

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
 
// Function that returns the count of
// factors that are perfect squares
static int noOfFactors(int N)
{
    if (N == 1)
        return 1;
 
    // Stores the count of number
    // of times a prime number
    // divides N.
    int count = 0;
 
    // Stores the number of factors
    // that are perfect square
    int ans = 1;
 
    // Count number of 2's
    // that divides N
    while (N % 2 == 0)
    {
        count++;
        N = N / 2;
    }
 
    // Calculate ans according
    // to above formula
    ans *= (count / 2 + 1);
 
    // Check for all the possible
    // numbers that can divide it
    for(int i = 3; i * i <= N; i = i + 2)
    {
        count = 0;
 
        // Check the number of
        // times prime number
        // i divides it
        while (N % i == 0)
        {
            count++;
            N = N / i;
        }
 
        // Calculate ans according
        // to above formula
        ans *= (count / 2 + 1);
    }
 
    // Return final count
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 100;
 
    System.out.print(noOfFactors(N));
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program to implement
# the above approach
 
# Function that returns the count of
# factors that are perfect squares
def noOfFactors(N):
 
    if (N == 1):
        return 1
 
    # Stores the count of number
    # of times a prime number
    # divides N.
    count = 0
 
    # Stores the number of factors
    # that are perfect square
    ans = 1
 
    # Count number of 2's
    # that divides N
    while (N % 2 == 0):
        count += 1
        N = N // 2
 
    # Calculate ans according
    # to above formula
    ans *= (count // 2 + 1)
 
    # Check for all the possible
    # numbers that can divide it
    i = 3
    while i * i <= N:
        count = 0
 
        # Check the number of
        # times prime number
        # i divides it
        while (N % i == 0):
            count += 1
            N = N // i
 
        # Calculate ans according
        # to above formula
        ans *= (count // 2 + 1)
        i += 2
     
    # Return final count
    return ans
 
# Driver Code
if __name__ == "__main__":
     
    N = 100
 
    print(noOfFactors(N))
 
# This code is contributed by chitranayal

C#

// C# program to implement
// the above approach
using System;
 
class GFG{
 
// Function that returns the count of
// factors that are perfect squares
static int noOfFactors(int N)
{
    if (N == 1)
        return 1;
 
    // Stores the count of number
    // of times a prime number
    // divides N.
    int count = 0;
 
    // Stores the number of factors
    // that are perfect square
    int ans = 1;
 
    // Count number of 2's
    // that divides N
    while (N % 2 == 0)
    {
        count++;
        N = N / 2;
    }
 
    // Calculate ans according
    // to above formula
    ans *= (count / 2 + 1);
 
    // Check for all the possible
    // numbers that can divide it
    for(int i = 3; i * i <= N; i = i + 2)
    {
        count = 0;
 
        // Check the number of
        // times prime number
        // i divides it
        while (N % i == 0)
        {
            count++;
            N = N / i;
        }
 
        // Calculate ans according
        // to above formula
        ans *= (count / 2 + 1);
    }
 
    // Return final count
    return ans;
}
 
// Driver Code
public static void Main(String[] args)
{
    int N = 100;
 
    Console.Write(noOfFactors(N));
}
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
 
// Javascript program for
// the above approach
 
// Function that returns the count of
// factors that are perfect squares
function noOfFactors(N)
{
    if (N == 1)
        return 1;
   
    // Stores the count of number
    // of times a prime number
    // divides N.
    let count = 0;
   
    // Stores the number of factors
    // that are perfect square
    let ans = 1;
   
    // Count number of 2's
    // that divides N
    while (N % 2 == 0)
    {
        count++;
        N = N / 2;
    }
   
    // Calculate ans according
    // to above formula
    ans *= (count / 2 + 1);
   
    // Check for all the possible
    // numbers that can divide it
    for(let i = 3; i * i <= N; i = i + 2)
    {
        count = 0;
   
        // Check the number of
        // times prime number
        // i divides it
        while (N % i == 0)
        {
            count++;
            N = N / i;
        }
   
        // Calculate ans according
        // to above formula
        ans *= (count / 2 + 1);
    }
   
    // Return final count
    return ans;
}
     
// Driver Code
     
   let N = 100;
   
  document.write(noOfFactors(N));
 
</script>

Producción:

Complejidad de Tiempo: Complejidad $O(\sqrt{N})$
de Espacio: O(1)

Publicación traducida automáticamente

Artículo escrito por rimjhim_25 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta