Find if nCr is divisible by the given prime | Function to return the highest power of p that divides n ! implementing Legendre Formula ; Return the highest power of p which divides n ! ; Function that returns true if nCr is divisible by p ; Find the highest powers of p that divide n ! , r ! and ( n - r ) ! ; If nCr is divisible by p ; Driver code
def getfactor ( n , p ) : NEW_LINE INDENT pw = 0 ; NEW_LINE while ( n ) : NEW_LINE INDENT n //= p ; NEW_LINE pw += n ; NEW_LINE DEDENT return pw ; NEW_LINE DEDENT def isDivisible ( n , r , p ) : NEW_LINE INDENT x1 = getfactor ( n , p ) ; NEW_LINE x2 = getfactor ( r , p ) ; NEW_LINE x3 = getfactor ( n - r , p ) ; NEW_LINE if ( x1 > x2 + x3 ) : NEW_LINE INDENT return True ; NEW_LINE DEDENT return False ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 7 ; r = 2 ; p = 7 ; NEW_LINE if ( isDivisible ( n , r , p ) ) : NEW_LINE INDENT print ( " Yes " ) ; NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) ; NEW_LINE DEDENT DEDENT