Dados dos números, hecho y n , encuentra la mayor potencia de n que divide a hecho. (factorial de hecho).
Ejemplos:
Input : fact = 5, n = 2 Output : 3 Explanation: Value of 5! is 120. The largest power of 2 that divides 120 is 8 (or 23 Input : fact = 146, n = 15 Output : 35
La idea se basa en la fórmula de Legendre que encuentra la mayor potencia de un número primo que divide a fact!. Encontramos todos los factores primos de n . Para cada factor primo encontramos la mayor potencia que divide a fact!. Finalmente devolvemos el mínimo de todos los poderes encontrados.
Ilustración :
fact = 146, n=15 First find the prime factor of 15 that are 3 and 5 then first divide with 3 and add i.e. Applying Legendre’s formula for prime factor 3. [146/3]+[48/3]+[16/3]+[5/3]+[1/3] = 70 48 + 16 + 5 + 1 + 0 = 70 There is 70 is maximum power of 3 prime number. 146! is divisible by 3^70 which is maximum. Applying Legendre’s formula for prime factor 5. [146/5]+[29/5]+[5/5]+[1/5] = 35 29 + 5 + 1 + 0 = 35 There is 35 is maximum power of 5 prime number.
El mínimo de dos potencias es 35, que es nuestra respuesta.
Nota: si hay múltiples potencias de un factor primo en n, dividimos la cuenta para obtener el valor máximo de potencia para este factor.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find largest power of
// a number (which may be composite) that
// divides factorial.
#include <bits/stdc++.h>
using namespace std;
// for find maximum power of prime number
// p which can divide fact number
int findPowerPrime(int fact, int p)
{
int res = 0;
while (fact > 0) {
res += fact / p;
fact /= p;
}
return res;
}
// Returns sum of all factors of n.
int findPowerComposite(int fact, int n)
{
// To store result (minimum power of a
// prime factor that divides fact! )
int res = INT_MAX;
// Traverse through all prime factors
// of n.
for (int i = 2; i <= sqrt(n); i++) {
// counter for count the
// power of prime number
int count = 0;
while (n % i == 0) {
count++;
n = n / i;
}
if (count > 0) {
// Maximum power of i that divides
// fact!. We divide by count to handle
// multiple occurrences of a prime factor.
int curr_pow = findPowerPrime(fact, i) / count;
res = min(res, curr_pow);
}
}
// This condition is to handle
// the case when n is a prime
// number greater than 2.
if (n >= 2) {
int curr_pow = findPowerPrime(fact, n);
res = min(res, curr_pow);
}
return res;
}
// Driver code
int main()
{
int fact = 146, n = 5;
// Function Call
cout << findPowerComposite(fact, n);
return 0;
}
Java
// Java program to find largest power of
// a number (which may be composite) that
// divides factorial.
class GFG {
// for find maximum power of prime number
// p which can divide fact number
static int findPowerPrime(int fact, int p)
{
int res = 0;
while (fact > 0) {
res += fact / p;
fact /= p;
}
return res;
}
// Returns sum of all factors of n.
static int findPowerComposite(int fact, int n)
{
// To store result (minimum power of a
// prime factor that divides fact! )
int res = Integer.MAX_VALUE;
// Traverse through all prime factors
// of n.
for (int i = 2; i <= Math.sqrt(n); i++)
{
// counter for count the
// power of prime number
int count = 0;
if (n % i == 0)
{
count++;
n = n / i;
}
if (count > 0)
{
// Maximum power of i that divides
// fact!. We divide by count to
// handle multiple occurrences of
// a prime factor.
int curr_pow
= findPowerPrime(fact, i) / count;
res = Math.min(res, curr_pow);
}
}
// This condition is to handle
// the case when n is a prime
// number greater than 2.
if (n >= 2) {
int curr_pow = findPowerPrime(fact, n);
res = Math.min(res, curr_pow);
}
return res;
}
// Driver code
public static void main(String[] args)
{
int fact = 146, n = 5;
// Function Call
System.out.println(findPowerComposite(fact, n));
}
}
// This code is contributed by prerna saini
Python3
# Python program to find largest power of # a number (which may be composite) that # divides factorial. import math # For find maximum power of prime number # p which can divide fact number def findPowerPrime(fact, p): res = 0 while fact: res += fact // p fact //= p return res # Returns sum of all factors of n def findPowerComposite(fact, n): # To store result (minimum power of a # prime factor that divides fact! ) res = math.inf # Traverse through all prime factors # of n. for i in range(2, int(n**0.5) + 1): # Counter for count the # power of prime number count = 0 if not n % i: count += 1 n = n // i if count: # Maximum power of i that divides # fact!. We divide by count to handle # multiple occurrences of a prime factor. curr_pow = findPowerPrime(fact, i) // count res = min(res, curr_pow) # This condition is to handle # the case when n is a prime # number greater than 2. if n >= 2: curr_pow = findPowerPrime(fact, n) res = min(res, curr_pow) return res # Driver code fact = 146 n = 5 # Function Call print(findPowerComposite(fact, n)) # This code is contributed by Ansu Kumari
C#
// C# program to find largest power of
// a number (which may be composite) that
// divides factorial.
using System;
class GFG {
// for find maximum power of prime number
// p which can divide fact number
static int findPowerPrime(int fact, int p)
{
int res = 0;
while (fact > 0) {
res += fact / p;
fact /= p;
}
return res;
}
// Returns sum of all factors of n.
static int findPowerComposite(int fact, int n)
{
// To store result (minimum power of a
// prime factor that divides fact! )
int res = int.MaxValue;
// Traverse through all prime factors
// of n.
for (int i = 2; i <= Math.Sqrt(n); i++) {
// counter for count the
// power of prime number
int count = 0;
if (n % i == 0) {
count++;
n = n / i;
}
if (count > 0) {
// Maximum power of i that divides
// fact!. We divide by count to
// handle multiple occurrences of
// a prime factor.
int curr_pow
= findPowerPrime(fact, i) / count;
res = Math.Min(res, curr_pow);
}
}
// This condition is to handle
// the case when n is a prime
// number greater than 2.
if (n >= 2) {
int curr_pow = findPowerPrime(fact, n);
res = Math.Min(res, curr_pow);
}
return res;
}
// Driver code
public static void Main()
{
int fact = 146, n = 5;
// Function Call
Console.WriteLine(findPowerComposite(fact, n));
}
}
// This code is contributed by vt_m
PHP
<?php
// PHP program to find largest
// power of a number (which
// may be composite) that
// divides factorial.
// for find maximum power
// of prime number p which
// can divide fact number
function findPowerPrime($fact, $p)
{
$res = 0;
while ($fact > 0)
{
$res += intval($fact / $p);
$fact = intval($fact / $p);
}
return $res;
}
// Returns sum of
// all factors of n.
function findPowerComposite($fact, $n)
{
// To store result (minimum
// power of a prime factor
// that divides fact! )
$res = PHP_INT_MAX;
// Traverse through all
// prime factors of n.
for ($i = 2;
$i <= sqrt($n); $i++)
{
// counter for count the
// power of prime number
$count = 0;
if ($n % $i == 0)
{
$count++;
$n = intval($n / $i);
}
if ($count > 0)
{
// Maximum power of i
// that divides fact!.
// We divide by count
// to handle multiple
// occurrences of a
// prime factor.
$curr_pow = intval(findPowerPrime(
$fact, $i) / $count);
$res = min($res, $curr_pow);
}
}
// This condition is to
// handle the case when
// n is a prime number
// greater than 2.
if ($n >= 2)
{
$curr_pow = findPowerPrime($fact, $n);
$res = min($res, $curr_pow);
}
return $res;
}
// Driver code
$fact = 146; $n = 5;
// Function Call
echo (findPowerComposite($fact, $n));
// This code is contributed by
// Manish Shaw(manishshaw1)
?>
Javascript
<script>// Javascript program to find largest
// power of a number (which
// may be composite) that
// divides factorial.
// for find maximum power
// of prime number p which
// can divide fact number
function findPowerPrime(fact, p)
{
let res = 0;
while (fact > 0)
{
res += parseInt(fact / p);
fact = parseInt(fact / p);
}
return res;
}
// Returns sum of
// all factors of n.
function findPowerComposite(fact, n)
{
// To store result (minimum
// power of a prime factor
// that divides fact! )
let res = Number.MAX_SAFE_INTEGER;
// Traverse through all
// prime factors of n.
for (let i = 2;
i <= Math.sqrt(n); i++)
{
// counter for count the
// power of prime number
count = 0;
if (n % i == 0)
{
count++;
n = parseInt(n / i);
}
if (count > 0)
{
// Maximum power of i
// that divides fact!.
// We divide by count
// to handle multiple
// occurrences of a
// prime factor.
curr_pow = parseInt(findPowerPrime(
fact, i) / count);
res = Math.min(res, curr_pow);
}
}
// This condition is to
// handle the case when
// n is a prime number
// greater than 2.
if (n >= 2)
{
curr_pow = findPowerPrime(fact, n);
res = Math.min(res, curr_pow);
}
return res;
}
// Driver code
let fact = 146;
let n = 5;
// Function Call
document.write(findPowerComposite(fact, n));
// This code is contributed by _saurabh_jaiswal
</script>
Producción
35
Complejidad de tiempo: O(sqrt(n)*log(n))
Espacio auxiliar: O(1), ya que no se utiliza espacio adicional
Publicación traducida automáticamente
Artículo escrito por DevanshuAgarwal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA