查找nCr是否可被C ++中的给定素数整除
假设存在三个变量N，R和P。N和R用于获得NCR，并且P是素数。我们必须找到NCR是否可被P整除。假设我们有一些数字N=7，R=2和P=3，那么7C2=21，这可被3整除，因此输出为真。
我们知道NCR=N！/（R！*（N–R）！）。我们将使用Legendre公式获得P的最大幂，该幂除以N!,R!。和（N–R）！为了使NCR被P整除，条件是N！>R！+(N-R)！
示例
#include <iostream>
using namespace std;
int getPower(int n, int p) {
int pow = 0;
while (n) {
n /= p;
pow += n;
}
return pow;
}
bool isDivisibleByP(int n, int r, int p) {
// Find the highest powers of p
// that divide n!, r! and (n - r)!
int x1 = getPower(n, p);
int x2 = getPower(r, p);
int x3 = getPower(n - r, p);
if (x1 > x2 + x3)
return true;
return false;
}
int main() {
int n = 7, r = 2, p = 7;
if (isDivisibleByP(n, r, p))
cout << "nCr is divisible by P";
else
cout << "nCr is not divisible by P";
}输出结果
nCr is divisible by P