一个数字的质因数的乘积

Question

对于给定的数字X，最有效的计算其 质数 因子乘积的方法是什么？ 是否有一种可以不实际进行因式分解的方法来完成此操作？ 注意-所需为质数因子的乘积（所有质数的幂次都为1）。

- LTim

---

这不是很清楚。天真地想，答案只是 return X; ... - Oliver Charlesworth

并不是说我的无知有多少价值，但我不知道在不知道X的质因数的情况下计算任意X的无平方因子核的方法。 - DSM

据我所知，答案是否定的，没有比分解该数字更有效（从大O角度来看）地推导出单个数字的质因数积。但是，您可能会在http://cs.stackechange.com上找到更有见地/专业的答案。 - RBarryYoung

稍微思考一下，计算n的质因数p的乘积product(p)似乎在计算上等效于计算欧拉函数product(p-1)。我已经编写了程序来执行此操作，它们都需要以某种方式对n进行因式分解。事实上，RSA加密方案的强度依赖于Totient(n)与n的因式分解同样难以计算。 - RBarryYoung

你的问题不够清晰。你是想要所有质因数的乘积，还是只需要唯一的质因数的乘积？也就是说，如果给定数字28，它的质因数为(2,2,7)，你希望得到的答案是14吗？ - Jim Mischel

是的，独特质因数的乘积。 - LTim

Answer 1

这个答案解决了你问题的后半部分 - 即是否可能计算素因子的乘积而不进行因数分解。这个答案表明这是可能的，并且展示了一种比朴素的因数分解方法更有效的方法。但是，正如评论中所指出的那样，这种提出的方法仍然不如使用更高级的方法进行因数分解那么有效。

让k成为该数字的立方根。

检查所有小于或等于k的质数并除去我们发现的任何一个。

现在我们知道得到的数字是大于k的质数的乘积，因此它必须是1、单个质数或2个质数的乘积。（它不能有超过2个质数，因为k是该数字的立方根。）

我们可以通过简单地测试该数字是否为完全平方来检测它是否是2个质数的乘积。

这些结果使我们能够在假定我们已经预先计算了质数列表的情况下以O(n^(1/3) / log(n)) 的复杂度计算结果。

例1

假设我们有数字9409。

立方根是21.1，因此我们首先检查21以下的质数是否可以整除它。

它们中没有一个找到结果，因此我们计算sqrt并找到9409 == 97 ** 2。

这意味着答案是97。

例2

假设我们有数字9797。

立方根是21.4，因此我们检查21以下的质数是否可以整除它。

它们中没有一个找到结果，因此我们计算sqrt并发现9797不是完全平方数。

因此我们得出结论，答案是9797。（请注意，我们没有确定因数分解以计算出这个答案。实际上，因数分解是97 * 101。）

- Peter de Rivaz

---

这并不比分解该数字更有效率。 - RBarryYoung

@RBarryYoung 因式分解的复杂度是什么？我假设使用试除法，尝试所有小于该数平方根的质数。 - Peter de Rivaz

@PeterdeRvaz 因式分解是一个非常复杂和精密的领域，最好由Google和维基百科来回答，而不是我。然而，你应该首先问自己的问题是，“我提出的方法是否比因式分解更快或者仅仅是不同？” 到目前为止，答案是否，你所提出的所有方法也都是天真因式分解中常见的技巧。 - RBarryYoung

不错的技巧，让我们不必完全完成因数分解...但是真正复杂的因数分解算法要快得多。因此，与简单的试除法相比，这个技巧只有在与椭圆曲线因子分解等复杂算法相比时才值得使用。换句话说，如果您可以使用ECF，则使用它进行完整的因数分解比使用此技巧进行一半的试除法更快（当然，这是针对大数字而言）。 - Will Ness

21113*13=3718。立方根为15.49...所有质因数都小于它，所以在除掉它们后我们将得到1。或者我误解了你的方法？ - Bert te Velde

@BertteVelde 没错，最后你需要将找到的所有质因数相乘。 - Peter de Rivaz

Answer 2

Maple和Mathematica都通过因数分解并将每个质数的一个副本乘回来来计算一个数字的无平方因子核（参见https://oeis.org/A007947），因此我怀疑是否已知有更好的方法。

- Edward Doolittle

Answer 3

另一种方法是从数字本身开始。显然，它是所有质因数的乘积。您想要删除所有幂大于一的因子。因此，如果数字有因子2，您并不介意，但如果它有因子4（2 ^ 2），则会介意。我们可以通过删除额外的因子来解决问题。

简单伪代码：

method removeHigherPrimePowers(number)
  temp <- number
  primes <- [2, 3, 5, 7 ...]
  for each p in primes
    factor <- p * p  // factor = 4, 9, 25, ...
    while (temp MOD factor = 0)
      temp <- temp / p  // Remove extra factor of p
    endwhile
  endfor
  return temp
endmethod

正在对数字进行因式分解，但是因式分解有些隐蔽。所有这些MOD语句都执行相同的工作。所保存的只是一定量的账目，跟踪到目前为止找到的因子并在最后将它们全部相乘。

正如Peter所说，您可以测试所有小于立方根的质数，然后检查剩余的数字是否为平方数。

- rossum

---

当temp MOD factor != 0时，while循环退出。temp的值在每次循环中更改，即temp <- temp / p。在某个时刻，循环将会退出。 - rossum

它将在任何具有无限存储空间以下的计算机上终止。primes列表的大小可以根据输入测试数字X的值范围进行设置，该值未在问题中指定。我出于这个原因而保持了开放状态。 - rossum