Requisito previo: imprimir todos los factores primos y sus potencias
Dados los números naturales N y P , la tarea es encontrar la potencia de P en la factorización de N. .
Ejemplos
Entrada: N = 4, P = 2
Salida: 3
Explicación:
¡Potencia de 2 en la descomposición en factores primos de 4! = 24 es 3Entrada: N = 24, P = 4
Salida: 11
Enfoque ingenuo: la idea es encontrar la potencia de P para cada número del 1 al N y sumarlos, como sabemos, durante la multiplicación se suma la potencia.
Complejidad de tiempo: O(N*P)
Enfoque eficiente:
¡ Encontrar la potencia del número P en N! Haz lo siguiente:
- Encuentre todos los factores primos del número P con su frecuencia usando el enfoque discutido en este artículo. Guarda los factores primos con su frecuencia en el mapa .
- ¡ Encuentra la potencia de todos los factores primos de P en la factorización de N! usando el enfoque discutido en este artículo.
- Divide cada potencia obtenida en los pasos anteriores por su frecuencia correspondiente en el mapa .
- Almacene el resultado de los pasos anteriores en una array y un mínimo de esos elementos dará la potencia de P en la factorización de N!.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the power
// of P in N!
#include <bits/stdc++.h>
using namespace std;
// Map to store all the prime
// factors of P
unordered_map<int, int> Map;
// Function to find the prime
// factors of N im Map
void findPrimeFactors(int N)
{
int i;
// Clear map
Map.clear();
// Check for factors of 2
while (N % 2 == 0) {
Map[2] += 1;
N /= 2;
}
// Find all the prime factors
for (i = 3; i <= sqrt(N); i += 2) {
// If i is a factors
// then increase the
// frequency of i
while (N % i == 0) {
Map[i] += 1;
N /= i;
}
}
if (N > 2) {
Map[N] += 1;
}
}
// Function to find the power
// of prime number P in N!
int PowInFactN(int N, int P)
{
int ans = 0;
int temp = P;
// Loop until temp <= N
while (temp <= N) {
// Add the number of
// numbers divisible
// by N
ans += N / temp;
// Each time multiply
// temp by P
temp = temp * P;
}
// Returns ans
return ans;
}
// Function that find the
// powers of any P in N!
int findPowers(int N, int P)
{
// Find all prime factors
// of number P
findPrimeFactors(P);
// To store the powers of
// all prime factors
vector<int> Powers;
// Traverse the map
for (auto& it : Map) {
// Prime factor and
// corres. powers
int primeFac = it.first;
int facPow = it.second;
// Find power of prime
// factor primeFac
int p = PowInFactN(N,
primeFac);
// Divide frequency by
// facPow
p /= facPow;
// Store the power of
// primeFac^facPow
Powers.push_back(p);
}
// Return the minimum
// element in Power array
return *min_element(Powers.begin(),
Powers.end());
}
// Driver's Code
int main()
{
int N = 24, P = 4;
// Function to find power of
// P in N!
cout << findPowers(N, P);
return 0;
}
Java
// Java program to find the power
// of P in N!
import java.util.*;
class GFG{
// Map to store all the prime
// factors of P
static HashMap<Integer,Integer> Map = new HashMap<Integer,Integer>();
// Function to find the prime
// factors of N im Map
static void findPrimeFactors(int N)
{
int i;
// Clear map
Map.clear();
// Check for factors of 2
while (N % 2 == 0) {
if(Map.containsKey(2))
Map.put(2, Map.get(2) + 1);
else
Map.put(2, 1);
N /= 2;
}
// Find all the prime factors
for (i = 3; i <= Math.sqrt(N); i += 2) {
// If i is a factors
// then increase the
// frequency of i
while (N % i == 0) {
if(Map.containsKey(i))
Map.put(i, Map.get(i) + 1);
else
Map.put(i, 1);
N /= i;
}
}
if (N > 2) {
if(Map.containsKey(N))
Map.put(N, Map.get(N) + 1);
else
Map.put(N, 1);
}
}
// Function to find the power
// of prime number P in N!
static int PowInFactN(int N, int P)
{
int ans = 0;
int temp = P;
// Loop until temp <= N
while (temp <= N) {
// Add the number of
// numbers divisible
// by N
ans += N / temp;
// Each time multiply
// temp by P
temp = temp * P;
}
// Returns ans
return ans;
}
// Function that find the
// powers of any P in N!
static int findPowers(int N, int P)
{
// Find all prime factors
// of number P
findPrimeFactors(P);
// To store the powers of
// all prime factors
Vector<Integer> Powers = new Vector<Integer>();
// Traverse the map
for (Map.Entry<Integer, Integer> it : Map.entrySet()) {
// Prime factor and
// corres. powers
int primeFac = it.getKey();
int facPow = it.getValue();
// Find power of prime
// factor primeFac
int p = PowInFactN(N,
primeFac);
// Divide frequency by
// facPow
p /= facPow;
// Store the power of
// primeFac^facPow
Powers.add(p);
}
// Return the minimum
// element in Power array
return Collections.min(Powers);
}
// Driver's Code
public static void main(String[] args)
{
int N = 24, P = 4;
// Function to find power of
// P in N!
System.out.print(findPowers(N, P));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to find the power
# of P in N!
import math
# Map to store all
# the prime factors of P
Map = {}
# Function to find the prime
# factors of N im Map
def findPrimeFactors(N):
# Clear map
Map.clear()
# Check for factors of 2
while (N % 2 == 0):
if 2 in Map:
Map[2] += 1
else:
Map[2] = 1
N = N // 2
# Find all the prime factors
for i in range(3, int(math.sqrt(N)) + 1, 2):
# If i is a factors
# then increase the
# frequency of i
while (N % i == 0):
if i in Map:
Map[i] += 1
else:
Map[i] = 1
N = N // i
if (N > 2):
if N in Map:
Map[N] += 1
else:
Map[N] = 1
# Function to find the power
# of prime number P in N!
def PowInFactN(N, P):
ans = 0
temp = P
# Loop until temp <= N
while (temp <= N):
# Add the number of
# numbers divisible
# by N
ans = ans + (N // temp)
# Each time multiply
# temp by P
temp = temp * P
# Returns ans
return ans
# Function that find the
# powers of any P in N!
def findPowers(N, P):
# Find all prime factors
# of number P
findPrimeFactors(P)
# To store the powers of
# all prime factors
Powers = []
# Traverse the map
for it1, it2 in Map.items():
# Prime factor and
# corres. powers
primeFac = it1
facPow = it2
# Find power of prime
# factor primeFac
p = PowInFactN(N, primeFac)
# Divide frequency by
# facPow
p = p // facPow
# Store the power of
# primeFac^facPow
Powers.append(p)
# Return the minimum
# element in Power array
return min(Powers)
N, P = 24, 4
# Driver code
if __name__ == "__main__":
# Function to find
# power of P in N!
print(findPowers(N, P))
# This code is contributed by divyeshrabadiya07
C#
// C# program to find the power
// of P in N!
using System;
using System.Linq;
using System.Collections.Generic;
class GFG{
// Map to store all the prime
// factors of P
static Dictionary<int,int> Map = new Dictionary<int,int>();
// Function to find the prime
// factors of N im Map
static void findPrimeFactors(int N)
{
int i;
// Clear map
Map.Clear();
// Check for factors of 2
while (N % 2 == 0) {
if(Map.ContainsKey(2))
Map[2] = Map[2] + 1;
else
Map.Add(2, 1);
N /= 2;
}
// Find all the prime factors
for (i = 3; i <= Math.Sqrt(N); i += 2) {
// If i is a factors
// then increase the
// frequency of i
while (N % i == 0) {
if(Map.ContainsKey(i))
Map[i] = Map[i] + 1;
else
Map.Add(i, 1);
N /= i;
}
}
if (N > 2) {
if(Map.ContainsKey(N))
Map[N] =Map[N] + 1;
else
Map.Add(N, 1);
}
}
// Function to find the power
// of prime number P in N!
static int PowInFactN(int N, int P)
{
int ans = 0;
int temp = P;
// Loop until temp <= N
while (temp <= N) {
// Add the number of
// numbers divisible
// by N
ans += N / temp;
// Each time multiply
// temp by P
temp = temp * P;
}
// Returns ans
return ans;
}
// Function that find the
// powers of any P in N!
static int findPowers(int N, int P)
{
// Find all prime factors
// of number P
findPrimeFactors(P);
// To store the powers of
// all prime factors
List<int> Powers = new List<int>();
// Traverse the map
foreach (KeyValuePair<int, int> it in Map) {
// Prime factor and
// corres. powers
int primeFac = it.Key;
int facPow = it.Value;
// Find power of prime
// factor primeFac
int p = PowInFactN(N,
primeFac);
// Divide frequency by
// facPow
p /= facPow;
// Store the power of
// primeFac^facPow
Powers.Add(p);
}
// Return the minimum
// element in Power array
return Powers.Min();
}
// Driver's Code
public static void Main(String[] args)
{
int N = 24, P = 4;
// Function to find power of
// P in N!
Console.Write(findPowers(N, P));
}
}
// This code is contributed by sapnasingh4991
Javascript
// JavaScript program to find the power
// of P in N!
// Map to store all the prime
// factors of P
let map = new Map();
// unordered_map<int, int> Map;
// Function to find the prime
// factors of N im Map
function findPrimeFactors(N)
{
let i;
// Clear map
map.clear();
// Check for factors of 2
while (N % 2 == 0) {
if(map.has(2)){
map.set(2, map.get(2) + 1);
}
else{
map.set(2, 1);
}
N = Math.floor(N/2);
}
// Find all the prime factors
for (i = 3; i <= Math.sqrt(N); i += 2) {
// If i is a factors
// then increase the
// frequency of i
while (N % i == 0) {
if(map.has(i)){
map.set(i, Map.get(i) + 1);
}
else{
map.set(i, 1);
}
N = Math.floor(N/i);
}
}
if (N > 2) {
if(map.has(N)){
map.set(N, map.get(N) + 1);
}
else{
map.set(N, 1);
}
}
}
// Function to find the power
// of prime number P in N!
function PowInFactN(N, P)
{
let ans = 0;
let temp = P;
// Loop until temp <= N
while (temp <= N) {
// Add the number of
// numbers divisible
// by N
ans = ans + Math.floor(N / temp);
// Each time multiply
// temp by P
temp = temp * P;
}
// Returns ans
return ans;
}
// Function that find the
// powers of any P in N!
function findPowers(N, P)
{
// Find all prime factors
// of number P
findPrimeFactors(P);
// To store the powers of
// all prime factors
let Powers = new Array();
// Traverse the map
for (const [key,value] of map.entries()) {
// Prime factor and
// corres. powers
let primeFac = key;
let facPow = value;
// Find power of prime
// factor primeFac
let p = PowInFactN(N, primeFac);
// Divide frequency by
// facPow
p = Math.floor(p/facPow);
// Store the power of
// primeFac^facPow
Powers.push(p);
}
// Return the minimum
// element in Power array
return Math.min(...Powers);
}
// Driver's Code
let N = 24;
let P = 4;
// Function to find power of
// P in N!
console.log(findPowers(N, P));
// The code is contributed by Gautam goel (gautamgoel962)
Producción:
11
Complejidad de tiempo: O(sqrt(P)*(log P N))
Espacio auxiliar: O(sqrt(P))
Publicación traducida automáticamente
Artículo escrito por RishavSinghMehta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA