Find if nCr is divisible by the given prime | C ++ implementation of the 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 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
#include <bits/stdc++.h> NEW_LINE #define ll  long long int NEW_LINE using namespace std ; int getfactor ( int n , int p ) { int pw = 0 ; while ( n ) { n /= p ; pw += n ; } return pw ; } bool 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 true ; return false ; } int main ( ) { int n = 7 , r = 2 , p = 7 ; if ( isDivisible ( n , r , p ) ) cout << " Yes " ; else cout << " No " ; return 0 ; }