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