Número máximo de veces que N se puede dividir entre distintas potencias de números primos

Dado un número entero N , la tarea es calcular el número máximo de veces que N se puede dividir por un número entero K , donde K es una potencia de un número primo y el valor de K siempre es distinto.

Ejemplo:

Entrada: N = 24
Salida: 3
Explicación: En la primera operación, K = 2 (=2 ¹ ). Por lo tanto, el valor de N se convierte en N = 24/2 = 12. En la segunda operación, K = 3. Por lo tanto, N = 12/3 = 4. En la tercera operación, K = 4 (=2 2 ⁾ . Por lo tanto, N = 4/4 = 1, que no se puede dividir más. Por lo tanto, {2, 3, 4} es el mayor conjunto de 3 enteros que tienen distintas potencias de números primos que pueden dividir a N.

Entrada: N = 100
Salida: 2

Enfoque : El problema dado se puede resolver utilizando un enfoque codicioso . La idea es dividir el número por todos sus factores primos en orden creciente de su valor y potencia. Iterar usando una variable i en el rango [2, √N] y si i divide N , entonces divide N con potencias crecientes de i (es decir, 1, 2, 3…) hasta que sea divisible con ella. Mantener la cuenta del número de divisiones en una variable que es la respuesta requerida.

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

// C++ program of th above approach
#include <bits/stdc++.h>
using namespace std;
 
// Program to find maximum number of
// times N can be divided by distinct
// powers of prime integers
int maxDivisions(int N)
{
    // Stores the required count
    int cnt = 0;
 
    int range = sqrt(N);
 
    // Loop to iterate in range [2, √N]
    for (int i = 2; i <= range; i++) {
 
        // If i divides N
        if (N % i == 0) {
            int j = i;
 
            // Divide N with increasing
            // powers of i
            while (N % j == 0 && N) {
                N = N / j;
                // Update j
                j *= i;
 
                // Increment cnt
                cnt++;
            }
 
            // Remove the remaining power
            // of i to avoid repetition
            while (N % i == 0) {
                N /= i;
            }
        }
    }
 
    // Return Answer
    return cnt;
}
 
// Driver Code
int main()
{
    int N = 100;
    cout << maxDivisions(N);
    return 0;
}

// JAVA program of th above approach
import java.util.*;
class GFG
{
 
  // Program to find maximum number of
  // times N can be divided by distinct
  // powers of prime integers
  public static int maxDivisions(int N)
  {
 
    // Stores the required count
    int cnt = 0;
 
    double range = Math.sqrt(N);
 
    // Loop to iterate in range [2, √N]
    for (int i = 2; i <= range; i++) {
 
      // If i divides N
      if (N % i == 0) {
        int j = i;
 
        // Divide N with increasing
        // powers of i
        while (N % j == 0 && N != 0) {
          N = N / j;
          // Update j
          j *= i;
 
          // Increment cnt
          cnt++;
        }
 
        // Remove the remaining power
        // of i to avoid repetition
        while (N % i == 0) {
          N /= i;
        }
      }
    }
 
    // Return Answer
    return cnt;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int N = 100;
    System.out.print(maxDivisions(N));
  }
}
 
// This code is contributed by Taranpreet

# Python code for the above approach
from math import ceil, sqrt
 
# Program to find maximum number of
# times N can be divided by distinct
# powers of prime integers
def maxDivisions(N):
 
    # Stores the required count
    cnt = 0;
 
    _range = ceil(sqrt(N));
 
    # Loop to iterate in range [2, √N]
    for i in range(2, _range + 1):
 
        # If i divides N
        if (N % i == 0):
            j = i;
 
            # Divide N with increasing
            # powers of i
            while (N % j == 0 and N):
                N = N / j;
                # Update j
                j *= i;
 
                # Increment cnt
                cnt += 1
 
            # Remove the remaining power
            # of i to avoid repetition
            while (N % i == 0):
                N /= i;
             
    # Return Answer
    return cnt;
 
# Driver Code
N = 100;
print(maxDivisions(N));
 
# This code is contributed by gfgking

// C# program to implement
// the above approach
using System;
 
class GFG
{
 
// Program to find maximum number of
  // times N can be divided by distinct
  // powers of prime integers
  public static int maxDivisions(int N)
  {
 
    // Stores the required count
    int cnt = 0;
 
    double range = Math.Sqrt(N);
 
    // Loop to iterate in range [2, √N]
    for (int i = 2; i <= range; i++) {
 
      // If i divides N
      if (N % i == 0) {
        int j = i;
 
        // Divide N with increasing
        // powers of i
        while (N % j == 0 && N != 0) {
          N = N / j;
          // Update j
          j *= i;
 
          // Increment cnt
          cnt++;
        }
 
        // Remove the remaining power
        // of i to avoid repetition
        while (N % i == 0) {
          N /= i;
        }
      }
    }
 
    // Return Answer
    return cnt;
  }
 
// Driver Code
public static void Main()
{
    int N = 100;
    Console.Write(maxDivisions(N));
}
}
 
// This code is contributed by sanjoy_62.

<script>
        // JavaScript code for the above approach
 
        // Program to find maximum number of
        // times N can be divided by distinct
        // powers of prime integers
        function maxDivisions(N)
        {
         
            // Stores the required count
            let cnt = 0;
 
            let range = Math.sqrt(N);
 
            // Loop to iterate in range [2, √N]
            for (let i = 2; i <= range; i++) {
 
                // If i divides N
                if (N % i == 0) {
                    let j = i;
 
                    // Divide N with increasing
                    // powers of i
                    while (N % j == 0 && N) {
                        N = N / j;
                        // Update j
                        j *= i;
 
                        // Increment cnt
                        cnt++;
                    }
 
                    // Remove the remaining power
                    // of i to avoid repetition
                    while (N % i == 0) {
                        N /= i;
                    }
                }
            }
 
            // Return Answer
            return cnt;
        }
 
        // Driver Code
        let N = 100;
        document.write(maxDivisions(N));
 
       // This code is contributed by Potta Lokesh
    </script>

2

Complejidad de Tiempo: O(√N)
Espacio Auxiliar: O(1)