algorithm - 作为某个整数 n 中的一个因子存在的最大阶乘数

Question

我正在设计一种算法来找到作为某个整数 n 中的一个因子存在的最大阶乘数。这个问题在 RGDormey 的“如何通过计算机解决”中给出。你能帮我设计算法吗..答案必须是整数n的一个因子，也是一个阶乘数..

我想到的解决方案：

首先确认整数不是素数。如果素数，没有进一步的解决方案可能..

如果不是素数，找出整数的最大因子

检查它是否是阶乘数..

如果是，那就是答案

如果不是，找出整数的第二大因子..

检查它是否是阶乘数...

等等..

score 4 · Accepted Answer

将 N 除以 1，然后将结果除以 2，然后将结果除以 3，...然后除以 k+1。一旦 k+1 没有整数结果，k! 是一个答案。

score 2 · Accepted Answer

您正在寻找进入整数的最大阶乘，因此您只需要稳步增加您的因数。即检查生成的整数是否可被 2、3、4 等整除...第一次失败时，您知道没有更大的阶乘将除以您的整数。例如，如果您的整数可以被 2 ... 6 整除，但不能被 7 整除，那么您知道答案是 6！。

score 0 · Accepted Answer

考虑到阶乘的性质非常非常大非常快......我很想尝试直接划分它。首先找到小于您的数字的最大阶乘...然后通过除法开始检查：让 N 成为您的数字。让阶乘 f(fac,num) 成为您的阶乘函数，它返回的阶乘小于您的数字。这样的数字！= fac 然后执行以下操作：

检查 (N % fac)==0; 否则尝试 (N*num) % fac 然后 (N* (num)*(num-1)) % fac

你需要的答案是（num）在第一种情况下（num-1）在第二种情况下，依此类推

score 0 · Accepted Answer

long prod = 1;
long maxFactor = 1;

for(long i=2; i<=n && prod< n && n%i==0 ;i++){

    prod  = prod*i;
    if(n%prod == 0) maxFactor = prod;
}

这n是我们需要找出其最大阶乘因子的数字，并且 macFactor 的最终值是最终解决方案。

注：数的因数也是数的因数。

如果因子是阶乘值，那么它必须是从 1 开始的连续整数的乘积（换句话说，它应该是除自身之外的其他因子的乘积）

score 0 · Accepted Answer

#include<stdio.h>
main()
{
      int i,n;
      scanf("%d",&n);
      for(i=2;n>1&&n%i==0;i++)
      n/=i;
      printf("%d",i-1);
}

n 是输入数

5 回答 5