Number of trailing zeroes in base B representation of N ! | C # program to find the number of trailing zeroes in base B representation of 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 B ; Returns largest power of B that divides N ! ; calculating minimum power of all the prime factors of B ; Driver code
using System ; using System . Collections . Generic ; class GFG { public class pair { public 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 List < pair > primeFactorsofB ( int B ) { List < pair > ans = new List < pair > ( ) ; for ( int i = 2 ; B != 1 ; i ++ ) { if ( B % i == 0 ) { int count = 0 ; while ( B % i == 0 ) { B = B / i ; count ++ ; } ans . Add ( new pair ( i , count ) ) ; } } return ans ; } static int largestPowerOfB ( int N , int B ) { List < pair > vec = new List < pair > ( ) ; vec = primeFactorsofB ( B ) ; int ans = int . MaxValue ; for ( int i = 0 ; i < vec . Count ; i ++ ) ans = Math . Min ( ans , findPowerOfP ( N , vec [ i ] . first ) / vec [ i ] . second ) ; return ans ; } public static void Main ( String [ ] args ) { Console . WriteLine ( largestPowerOfB ( 5 , 2 ) ) ; Console . WriteLine ( largestPowerOfB ( 6 , 9 ) ) ; } }