时间戳

首页 > 解决方案 > 阶乘的素数分解

math - 阶乘的素数分解

问题描述

是否可以在不实际计算阶乘的情况下找到阶乘的素因子？

我的意思是找到不是很大的阶乘的主要因素。您的算法应该跳过必须计算阶乘并从 n 导出素因子的步骤！其中 n <= 4000。

计算阶乘并找到它的主要除数非常容易，但是当输入大于 n=22 时，我的程序会崩溃。因此，我认为在不必计算阶乘的情况下完成整个过程会非常方便。

function decomp(n){
  var primeFactors = [];
  var fact = 1;

  for (var i = 2; i <= n; i++) {
     fact = fact * i;
  }

  while (fact % 2 === 0) {
    primeFactors.push(2);
    fact = fact/2;
  }

  var sqrtFact = Math.sqrt(fact);
    for (var i = 2; i <= sqrtFact; i++) {
    while (fact % i === 0) {
      primeFactors.push(i);
      fact = fact/i;
      }
  }

   return primeFactors;
}

我不期望任何代码或链接、示例和简短的大纲就足够了。

标签： mathprimesfactorial

解决方案

让我们考虑一个例子：10！= 2^8 * 3^4 * 5^2 * 7^1。我通过计算从 2 到 10 的每个数字的因数来计算：

 2: 2
 3: 3
 4: 2,2
 5: 5
 6: 2,3
 7: 7
 8: 2,2,2
 9: 3,3
10: 2,5

然后我只计算了每个因素。有 8 个 2（1 比 2、2 比 4、1 比 6、3 比 8 和 1 比 10）、4 个 3（1 比 3、1 比 6 和 2 比 9）、2 个 5（1 比 5 , 和 1 分之 1) 和一个 7 分 (7 分之一)。

在编写程序方面，只需保留一个计数器数组（它只需要与您要分解的最大阶乘的平方根一样大），并且对于从 2 到阶乘的每个数字，添加其计数计数器数组的因素。

这有帮助吗？

推荐阅读