Number of trailing zeroes in base B representation of N ! | Python 3 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
import sys NEW_LINE def findPowerOfP ( N , p ) : NEW_LINE INDENT count = 0 NEW_LINE r = p NEW_LINE while ( r <= N ) : NEW_LINE INDENT count += int ( N / r ) NEW_LINE r = r * p NEW_LINE DEDENT return count NEW_LINE DEDENT def primeFactorsofB ( B ) : NEW_LINE ' NEW_LINE INDENT ans = [ ] NEW_LINE i = 2 NEW_LINE while ( B != 1 ) : NEW_LINE INDENT if ( B % i == 0 ) : NEW_LINE INDENT count = 0 NEW_LINE while ( B % i == 0 ) : NEW_LINE INDENT B = int ( B / i ) NEW_LINE count += 1 NEW_LINE DEDENT ans . append ( ( i , count ) ) NEW_LINE DEDENT i += 1 NEW_LINE DEDENT return ans NEW_LINE DEDENT def largestPowerOfB ( N , B ) : NEW_LINE INDENT vec = [ ] NEW_LINE vec = primeFactorsofB ( B ) NEW_LINE ans = sys . maxsize NEW_LINE ans = min ( ans , int ( findPowerOfP ( N , vec [ 0 ] [ 0 ] ) / vec [ 0 ] [ 1 ] ) ) NEW_LINE return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT print ( largestPowerOfB ( 5 , 2 ) ) NEW_LINE print ( largestPowerOfB ( 6 , 9 ) ) NEW_LINE DEDENT