Factores del cubo perfecto de un número

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

Ejemplos:

Entrada: N = 27
Salida: 2
Explicación:
Hay 2 factores de 27 (1, 27) que son cubos perfectos

Entrada: N = 216
Salida: 4
Explicación:
Hay 4 factores de 216 (1, 8, 27, 216) que son cubo perfecto

Enfoque ingenuo: la idea ingenua es encontrar todos los factores posibles del número N dado y contar si cada factor es un cubo perfecto o no . En caso afirmativo, cuente este factor y verifique el siguiente factor.

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Enfoque eficiente: la idea es utilizar la observación matemática para encontrar una fórmula para calcular el número de factores que forman un cubo perfecto. El número de factores de un número viene dado por:

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

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

Factores de N que son cubo perfecto = (1 + a ₁ /3)*(1 + a ₂ /3)*…*(1 + a _n /3)
donde a ₁ , a ₂ , a ₃ , .., a _n son el recuento de distintos factores primos de N.

Ilustración:

Los factores de N = 216 son 2, 2, 2, 3, 3, 3.
Por lo tanto, la cantidad de factores que son cubos perfectos son (1 + 3/3) * (1 + 3/3) = 4. Los factores son 1, 8, 27 y 216.

Por lo tanto, encuentra el número de factores primos y aplica la fórmula anterior para encontrar el número de factores que son un cubo perfecto.

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

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns the count
// of factors that are perfect cube
int noOfFactors(int N)
{
    if (N == 1)
        return 1;
 
    // To store the count of number
    // of times a prime number
    // divides N.
    int count = 0;
 
    // To store the number of factors
    // that are perfect cube
    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 / 3 + 1);
 
    // Check for all the possible
    // numbers that can divide it
    for (int i = 3; i * i <= N; i = i + 2) {
        count = 0;
 
        // Loop to 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 / 3 + 1);
    }
 
    // Return final count
    return ans;
}
 
// Driver Code
int main()
{
    // Given number
    int N = 216;
 
    // Function Call
    cout << noOfFactors(N);
    return 0;
}

Java

// Java program for the above approach
class GFG{
 
// Function that returns the count
// of factors that are perfect cube
static int noOfFactors(int N)
{
    if (N == 1)
        return 1;
 
    // To store the count of number
    // of times a prime number
    // divides N.
    int count = 0;
 
    // To store the number of factors
    // that are perfect cube
    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 / 3 + 1);
 
    // Check for all the possible
    // numbers that can divide it
    for(int i = 3; i * i <= N; i = i + 2)
    {
        count = 0;
 
        // Loop to 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 / 3 + 1);
    }
 
    // Return final count
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given number
    int N = 216;
 
    // Function call
    System.out.print(noOfFactors(N));
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 program for the above approach
 
# Function that returns the count
# of factors that are perfect cube
def noofFactors(N):
     
    if N == 1:
        return 1
         
    # To store the count of number
    # of times a prime number
    # divides N
    count = 0
 
    # To store the count of factors that
    # are perfect cube
    ans = 1
 
    # Count number of 2's that divides N
    while(N % 2 == 0):
        count += 1
        N //= 2
 
    # Calculate ans according
    # to above formula
    ans *= ((count // 3) + 1)
 
    # Check for all possible
    # numbers that can divide it
    i = 3
    while((i * i) <= N):
        count = 0
 
        # Loop to check the number
        # of times prime number
        # i divides it
        while(N % i == 0):
            count += 1
            N //= i
         
        # Calculate ans according
        # to above formula
        ans *= ((count // 3) + 1)
        i += 2
         
    return ans
 
# Driver Code
 
# Given number
N = 216
 
# Function call
print(noofFactors(N))
     
# This code is contributed by VirusBuddah_

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function that returns the count
// of factors that are perfect cube
static int noOfFactors(int N)
{
    if (N == 1)
        return 1;
 
    // To store the count of number
    // of times a prime number
    // divides N.
    int count = 0;
 
    // To store the number of factors
    // that are perfect cube
    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 / 3 + 1);
 
    // Check for all the possible
    // numbers that can divide it
    for(int i = 3; i * i <= N; i = i + 2)
    {
        count = 0;
 
        // Loop to 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 / 3 + 1);
    }
 
    // Return final count
    return ans;
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given number
    int N = 216;
 
    // Function call
    Console.Write(noOfFactors(N));
}
}
 
// This code is contributed by Rajput-Ji

Javascript

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

Producción:

Complejidad de tiempo: O(log(N))
Espacio auxiliar: 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