Largest power of k in n ! ( factorial ) where k may not be prime | JAVA 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
import java . util . * ; class GFG { static class pair { int first , second ; public pair ( int first , int second ) { this . first = first ; this . second = second ; } } static int findPowerOfP ( int n , int p ) { int count = 0 ; int r = p ; while ( r <= n ) { count += ( n / r ) ; r = r * p ; } return count ; } static Vector < pair > primeFactorsofK ( int k ) { Vector < pair > ans = new Vector < pair > ( ) ; for ( int i = 2 ; k != 1 ; i ++ ) { if ( k % i == 0 ) { int count = 0 ; while ( k % i == 0 ) { k = k / i ; count ++ ; } ans . add ( new pair ( i , count ) ) ; } } return ans ; } static int largestPowerOfK ( int n , int k ) { Vector < pair > vec = new Vector < pair > ( ) ; vec = primeFactorsofK ( k ) ; int ans = Integer . MAX_VALUE ; for ( int i = 0 ; i < vec . size ( ) ; i ++ ) ans = Math . min ( ans , findPowerOfP ( n , vec . get ( i ) . first ) / vec . get ( i ) . second ) ; return ans ; } public static void main ( String [ ] args ) { System . out . print ( largestPowerOfK ( 7 , 2 ) + "NEW_LINE"); System . out . print ( largestPowerOfK ( 10 , 9 ) + "NEW_LINE"); } }