Number of trailing zeroes in base B representation of N ! | CPP 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findPowerOfP ( int N , int p ) { int count = 0 ; int r = p ; while ( r <= N ) { count += ( N / r ) ; r = r * p ; } return count ; } vector < pair < int , int > > primeFactorsofB ( int B ) { vector < pair < int , int > > ans ; for ( int i = 2 ; B != 1 ; i ++ ) { if ( B % i == 0 ) { int count = 0 ; while ( B % i == 0 ) { B = B / i ; count ++ ; } ans . push_back ( make_pair ( i , count ) ) ; } } return ans ; } int largestPowerOfB ( int N , int B ) { vector < pair < int , int > > vec ; vec = primeFactorsofB ( B ) ; int ans = INT_MAX ; for ( int i = 0 ; i < vec . size ( ) ; i ++ ) ans = min ( ans , findPowerOfP ( N , vec [ i ] . first ) / vec [ i ] . second ) ; return ans ; } int main ( ) { cout << largestPowerOfB ( 5 , 2 ) << endl ; cout << largestPowerOfB ( 6 , 9 ) << endl ; return 0 ; }