Legendre 's formula (Given p and n, find the largest x such that p^x divides n!) | Returns largest power of p that divides n ! ; Initialize result ; Calculate x = n / p + n / ( p ^ 2 ) + n / ( p ^ 3 ) + ... . ; Driver program
def largestPower ( n , p ) : NEW_LINE INDENT x = 0 NEW_LINE while n : NEW_LINE INDENT n /= p NEW_LINE x += n NEW_LINE DEDENT return x NEW_LINE DEDENT n = 10 ; p = 3 NEW_LINE print ( " The largest power of % d that divides % d ! is % d " % ( p , n , largestPower ( n , p ) ) ) NEW_LINE