Finding powers of any number P in N ! | Python3 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 code ; Function to find power of P in N !
import math NEW_LINE Map = { } NEW_LINE def findPrimeFactors ( N ) : NEW_LINE INDENT Map . clear ( ) NEW_LINE while ( N % 2 == 0 ) : NEW_LINE INDENT if 2 in Map : NEW_LINE INDENT Map [ 2 ] += 1 NEW_LINE DEDENT else : NEW_LINE INDENT Map [ 2 ] = 1 NEW_LINE DEDENT N = N // 2 NEW_LINE DEDENT for i in range ( 3 , int ( math . sqrt ( N ) ) + 1 , 2 ) : NEW_LINE INDENT while ( N % i == 0 ) : NEW_LINE INDENT if i in Map : NEW_LINE INDENT Map [ i ] += 1 NEW_LINE DEDENT else : NEW_LINE INDENT Map [ i ] = 1 NEW_LINE DEDENT N = N // i NEW_LINE DEDENT DEDENT if ( N > 2 ) : NEW_LINE INDENT if N in Map : NEW_LINE INDENT Map [ N ] += 1 NEW_LINE DEDENT else : NEW_LINE INDENT Map [ N ] = 1 NEW_LINE DEDENT DEDENT DEDENT def PowInFactN ( N , P ) : NEW_LINE INDENT ans = 0 NEW_LINE temp = P NEW_LINE while ( temp <= N ) : NEW_LINE INDENT ans = ans + ( N // temp ) NEW_LINE temp = temp * P NEW_LINE DEDENT return ans NEW_LINE DEDENT def findPowers ( N , P ) : NEW_LINE INDENT findPrimeFactors ( P ) NEW_LINE Powers = [ ] NEW_LINE for it1 , it2 in Map . items ( ) : NEW_LINE INDENT primeFac = it1 NEW_LINE facPow = it2 NEW_LINE p = PowInFactN ( N , primeFac ) NEW_LINE p = p // facPow NEW_LINE Powers . append ( p ) NEW_LINE DEDENT return min ( Powers ) NEW_LINE DEDENT N , P = 24 , 4 NEW_LINE if __name__ == " _ _ main _ _ " : NEW_LINE INDENT print ( findPowers ( N , P ) ) NEW_LINE DEDENT