Find if nCr is divisible by the given prime | Java Implementation of above approach ; Function to return the highest power of p that divides n ! implementing Legendre Formula ; Return the highest power of p which divides n ! ; Function to return N digits number which is divisible by D ; Find the highest powers of p that divide n ! , r ! and ( n - r ) ! ; If nCr is divisible by p ; Driver code
import java . io . * ; class GFG { static int getfactor ( int n , int p ) { int pw = 0 ; while ( n != 0 ) { n /= p ; pw += n ; } return pw ; } static int isDivisible ( int n , int r , int p ) { int x1 = getfactor ( n , p ) ; int x2 = getfactor ( r , p ) ; int x3 = getfactor ( n - r , p ) ; if ( x1 > x2 + x3 ) return 1 ; return 0 ; } public static void main ( String [ ] args ) { int n = 7 , r = 2 , p = 7 ; if ( isDivisible ( n , r , p ) == 1 ) System . out . print ( " Yes " ) ; else System . out . print ( " No " ) ; } }