¡La mayor potencia de k en n! (factorial) donde k puede no ser primo

Posted on by Rudeus Greyrat

Dados dos números k y n, encuentra la mayor potencia de k que divide a n. 
Restricciones: 
 

 K > 1

Ejemplos: 
 

Input : n = 7, k = 2
Output : 4
Explanation : 7! = 5040
The largest power of 2 that
divides 5040 is 24.

Input : n = 10, k = 9
Output :  2
The largest power of 9 that
divides 10! is 92.

Hemos discutido una solución en la publicación a continuación cuando k siempre es primo.
Fórmula de Legendre (Dados p y n, ¡encontrar la x más grande tal que p^x divide a n!)
Ahora, para encontrar la potencia de cualquier número no primo k en n, primero encontramos todos los factores primos del número k junto con la cuenta del número de sus ocurrencias. Luego, para cada factor primo, contamos las ocurrencias usando la fórmula de Legendre que establece que la mayor potencia posible de un número primo p en n es ⌊n/p⌋ + ⌊n/(p 2 )⌋ + ⌊n/(p 3 )⌋ + ……
Sobre todos los factores primos p de K, el que tenga el valor mínimo de findPowerOfK(n, p)/count será nuestra respuesta donde count es el número de ocurrencias de p en k.
 

C++

// CPP program to find the largest power
// of k that divides n!
#include <bits/stdc++.h>
using namespace std;
 
// To find the power of a prime p in
// factorial N
int findPowerOfP(int n, int p)
{
    int count = 0;
    int r=p;
    while (r <= n) {
 
        // calculating floor(n/r)
        // and adding to the count
        count += (n / r);
 
        // increasing the power of p
        // from 1 to 2 to 3 and so on
        r = r * p;
    }
    return count;
}
 
// returns all the prime factors of k
vector<pair<int, int> > primeFactorsofK(int k)
{
    // vector to store all the prime factors
    // along with their number of occurrence
    // in factorization of k
    vector<pair<int, int> > ans;
 
    for (int i = 2; k != 1; i++) {
        if (k % i == 0) {
            int count = 0;
            while (k % i == 0) {
                k = k / i;
                count++;
            }
 
            ans.push_back(make_pair(i, count));
        }
    }
    return ans;
}
 
// Returns largest power of k that
// divides n!
int largestPowerOfK(int n, int k)
{
    vector<pair<int, int> > vec;
    vec = primeFactorsofK(k);
    int ans = INT_MAX;
    for (int i = 0; i < vec.size(); i++)
 
        // calculating minimum power of all
        // the prime factors of k
        ans = min(ans, findPowerOfP(n,
              vec[i].first) / vec[i].second);
 
    return ans;
}
 
// Driver code
int main()
{
    cout << largestPowerOfK(7, 2) << endl;
    cout << largestPowerOfK(10, 9) << endl;
    return 0;
}

Java

// JAVA program to find the largest power
// of k that divides n!
import java.util.*;
 
class GFG
{
     
static class pair
{
    int first, second;
    public pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
// To find the power of a prime p in
// factorial N
static int findPowerOfP(int n, int p)
{
    int count = 0;
    int r = p;
    while (r <= n)
    {
 
        // calculating Math.floor(n/r)
        // and adding to the count
        count += (n / r);
 
        // increasing the power of p
        // from 1 to 2 to 3 and so on
        r = r * p;
    }
    return count;
}
 
// returns all the prime factors of k
static Vector<pair > primeFactorsofK(int k)
{
    // vector to store all the prime factors
    // along with their number of occurrence
    // in factorization of k
    Vector<pair> ans = new Vector<pair>();
 
    for (int i = 2; k != 1; i++)
    {
        if (k % i == 0)
        {
            int count = 0;
            while (k % i == 0)
            {
                k = k / i;
                count++;
            }
 
            ans.add(new pair(i, count));
        }
    }
    return ans;
}
 
// Returns largest power of k that
// divides n!
static int largestPowerOfK(int n, int k)
{
    Vector<pair > vec = new Vector<pair>();
    vec = primeFactorsofK(k);
    int ans = Integer.MAX_VALUE;
    for (int i = 0; i < vec.size(); i++)
 
        // calculating minimum power of all
        // the prime factors of k
        ans = Math.min(ans, findPowerOfP(n,
            vec.get(i).first) / vec.get(i).second);
 
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    System.out.print(largestPowerOfK(7, 2) +"\n");
    System.out.print(largestPowerOfK(10, 9) +"\n");
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program to find the largest power
# of k that divides n!
import sys
 
# To find the power of a prime p in
# factorial N
def findPowerOfP(n, p) :
 
    count = 0
    r = p
    while (r <= n) :
 
        # calculating floor(n/r)
        # and adding to the count
        count += (n // r)
 
        # increasing the power of p
        # from 1 to 2 to 3 and so on
        r = r * p
      
    return count
 
# returns all the prime factors of k
def primeFactorsofK(k) :
 
    # vector to store all the prime factors
    # along with their number of occurrence
    # in factorization of k
    ans = []
    i = 2
    while k != 1 :
        if k % i == 0 :
            count = 0
            while k % i == 0 :
                k = k // i
                count += 1
            ans.append([i , count])
        i += 1
 
    return ans
 
# Returns largest power of k that
# divides n!
def largestPowerOfK(n, k) :
 
    vec = primeFactorsofK(k)
    ans = sys.maxsize
    for i in range(len(vec)) :
 
        # calculating minimum power of all
        # the prime factors of k
        ans = min(ans, findPowerOfP(n, vec[i][0]) // vec[i][1])
 
    return ans
 
print(largestPowerOfK(7, 2))
print(largestPowerOfK(10, 9))
 
# This code is contributed by divyesh072019

C#

// C# program to find the largest power
// of k that divides n!
using System;
using System.Collections.Generic;
 
class GFG
{
     
class pair
{
    public int first, second;
    public pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
 
// To find the power of a prime p in
// factorial N
static int findPowerOfP(int n, int p)
{
    int count = 0;
    int r = p;
    while (r <= n)
    {
 
        // calculating Math.Floor(n/r)
        // and adding to the count
        count += (n / r);
 
        // increasing the power of p
        // from 1 to 2 to 3 and so on
        r = r * p;
    }
    return count;
}
 
// returns all the prime factors of k
static List<pair > primeFactorsofK(int k)
{
    // vector to store all the prime factors
    // along with their number of occurrence
    // in factorization of k
    List<pair> ans = new List<pair>();
 
    for (int i = 2; k != 1; i++)
    {
        if (k % i == 0)
        {
            int count = 0;
            while (k % i == 0)
            {
                k = k / i;
                count++;
            }
 
            ans.Add(new pair(i, count));
        }
    }
    return ans;
}
 
// Returns largest power of k that
// divides n!
static int largestPowerOfK(int n, int k)
{
    List<pair > vec = new List<pair>();
    vec = primeFactorsofK(k);
    int ans = int.MaxValue;
    for (int i = 0; i < vec.Count; i++)
 
        // calculating minimum power of all
        // the prime factors of k
        ans = Math.Min(ans, findPowerOfP(n,
            vec[i].first) / vec[i].second);
 
    return ans;
}
 
// Driver code
public static void Main(String[] args)
{
    Console.Write(largestPowerOfK(7, 2) +"\n");
    Console.Write(largestPowerOfK(10, 9) +"\n");
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// JavaScript program to find the largest power
// of k that divides n!
 
class pair
{
    constructor(first,second)
    {
        this.first = first;
        this.second = second;
    }
}
 
// To find the power of a prime p in
// factorial N
function findPowerOfP(n,p)
{
    let count = 0;
    let r = p;
    while (r <= n)
    {
  
        // calculating Math.floor(n/r)
        // and adding to the count
        count += Math.floor(n / r);
  
        // increasing the power of p
        // from 1 to 2 to 3 and so on
        r = r * p;
    }
    return count;
}
 
// returns all the prime factors of k
function primeFactorsofK(k)
{
    // vector to store all the prime factors
    // along with their number of occurrence
    // in factorization of k
    let ans = [];
  
    for (let i = 2; k != 1; i++)
    {
        if (k % i == 0)
        {
            let count = 0;
            while (k % i == 0)
            {
                k = Math.floor(k / i);
                count++;
            }
  
            ans.push(new pair(i, count));
        }
    }
    return ans;
}
 
// Returns largest power of k that
// divides n!
function largestPowerOfK(n,k)
{
    let vec = [];
    vec = primeFactorsofK(k);
    let ans = Number.MAX_VALUE;
    for (let i = 0; i < vec.length; i++)
  
        // calculating minimum power of all
        // the prime factors of k
        ans = Math.min(ans, findPowerOfP(n,
            vec[i].first) / vec[i].second);
  
    return ans;
}
 
// Driver code
document.write(largestPowerOfK(7, 2) +"<br>");
document.write(largestPowerOfK(10, 9) +"<br>");
 
 
// This code is contributed by rag2127
 
</script>

Producción:  

4
2

Este artículo es una contribución de ShivamKD . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *