Finding powers of any number P in N ! | Java 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 !
import java . util . * ; class GFG { static HashMap < Integer , Integer > Map = new HashMap < Integer , Integer > ( ) ; static void findPrimeFactors ( int N ) { int i ; Map . clear ( ) ; while ( N % 2 == 0 ) { if ( Map . containsKey ( 2 ) ) Map . put ( 2 , Map . get ( 2 ) + 1 ) ; else Map . put ( 2 , 1 ) ; N /= 2 ; } for ( i = 3 ; i <= Math . sqrt ( N ) ; i += 2 ) { while ( N % i == 0 ) { if ( Map . containsKey ( i ) ) Map . put ( i , Map . get ( i ) + 1 ) ; else Map . put ( i , 1 ) ; N /= i ; } } if ( N > 2 ) { if ( Map . containsKey ( N ) ) Map . put ( N , Map . get ( N ) + 1 ) ; else Map . put ( N , 1 ) ; } } static int PowInFactN ( int N , int P ) { int ans = 0 ; int temp = P ; while ( temp <= N ) { ans += N / temp ; temp = temp * P ; } return ans ; } static int findPowers ( int N , int P ) { findPrimeFactors ( P ) ; Vector < Integer > Powers = new Vector < Integer > ( ) ; for ( Map . Entry < Integer , Integer > it : Map . entrySet ( ) ) { int primeFac = it . getKey ( ) ; int facPow = it . getValue ( ) ; int p = PowInFactN ( N , primeFac ) ; p /= facPow ; Powers . add ( p ) ; } return Collections . min ( Powers ) ; } public static void main ( String [ ] args ) { int N = 24 , P = 4 ; System . out . print ( findPowers ( N , P ) ) ; } }