Finding powers of any number P in N ! | C ++ program to find the power of P in N ! ; Map to store all the prime factors of P ; Function to find the prime factors of N im Map ; Clear map ; Check for factors of 2 ; Find all the prime factors ; If i is a factors then increase the frequency of i ; Function to find the power of prime number P in N ! ; Loop until temp <= N ; Add the number of numbers divisible by N ; Each time multiply temp by P ; Returns ans ; Function that find the powers of any P in N ! ; Find all prime factors of number P ; To store the powers of all prime factors ; Traverse the map ; Prime factor and corres . powers ; Find power of prime factor primeFac ; Divide frequency by facPow ; Store the power of primeFac ^ facPow ; Return the minimum element in Power array ; Driver 's Code ; Function to find power of P in N !
#include <bits/stdc++.h> NEW_LINE using namespace std ; unordered_map < int , int > Map ; void findPrimeFactors ( int N ) { int i ; Map . clear ( ) ; while ( N % 2 == 0 ) { Map [ 2 ] += 1 ; N /= 2 ; } for ( i = 3 ; i <= sqrt ( N ) ; i += 2 ) { while ( N % i == 0 ) { Map [ i ] += 1 ; N /= i ; } } if ( N > 2 ) { Map [ N ] += 1 ; } } int PowInFactN ( int N , int P ) { int ans = 0 ; int temp = P ; while ( temp <= N ) { ans += N / temp ; temp = temp * P ; } return ans ; } int findPowers ( int N , int P ) { findPrimeFactors ( P ) ; vector < int > Powers ; for ( auto & it : Map ) { int primeFac = it . first ; int facPow = it . second ; int p = PowInFactN ( N , primeFac ) ; p /= facPow ; Powers . push_back ( p ) ; } return * min_element ( Powers . begin ( ) , Powers . end ( ) ) ; } int main ( ) { int N = 24 , P = 4 ; cout << findPowers ( N , P ) ; return 0 ; }