Largest power of k in n ! ( factorial ) where k may not be prime | JavaScript program to find the largest power of k that divides n ! ; To find the power of a prime p in factorial N ; calculating Math . 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
class pair { constructor ( first , second ) { this . first = first ; this . second = second ; } } function findPowerOfP ( n , p ) { let count = 0 ; let r = p ; while ( r <= n ) { count += Math . floor ( n / r ) ; r = r * p ; } return count ; } function primeFactorsofK ( k ) { let ans = [ ] ; for ( let i = 2 ; k != 1 ; i ++ ) { if ( k % i == 0 ) { let count = 0 ; while ( k % i == 0 ) { k = Math . floor ( k / i ) ; count ++ ; } ans . push ( new pair ( i , count ) ) ; } } return ans ; } function largestPowerOfK ( n , k ) { let vec = [ ] ; vec = primeFactorsofK ( k ) ; let ans = Number . MAX_VALUE ; for ( let i = 0 ; i < vec . length ; i ++ ) ans = Math . min ( ans , findPowerOfP ( n , vec [ i ] . first ) / vec [ i ] . second ) ; return ans ; } document . write ( largestPowerOfK ( 7 , 2 ) + " " ) ; document . write ( largestPowerOfK ( 10 , 9 ) + " " ) ;