问数的素数乘积

EN

这个答案解决了你问题的后半部分--也就是说，在不考虑数字的情况下，能不能计算出素因子的乘积。这个答案表明这是可能的，并且展示了一种比简单的分解方法更有效的方法。然而，正如注释中所指出的，这种拟议的方法仍然不如使用更先进的方法分解数字那样有效。

设k是数字的立方根。

检查所有大小为k或更小的素数，并将我们找到的任何素数除以。

我们现在知道结果数是大于k的素数的乘积，所以它必须是1，一个素数，或者是2个素数的乘积。(它不能有超过2个素数，因为k是数字的立方根。)

我们可以通过简单的测试这个数字是否是一个完美的平方来检测它是否是两个素数的乘积。

这个结果允许我们计算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。)

Maple和Mathematica都是通过分解来计算一个数字的无平方核，然后再把每个素数的一个副本相乘(参见https://oeis.org/A007947)，所以我怀疑是否有更好的方法。

另一种方法是从数字本身开始。它显然是其所有主要因素的产物。你想用一个以上的力量消除所有的因素。因此，您不介意这个数字是否有一个因子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所说，您可以测试所有素数到立方体根，然后检查剩余的数是否为正方形。