LTi*_*Tim 6 algorithm primes number-theory
给定数字X,计算该数字的素因子乘积的最有效方法是什么？有没有办法在没有实际分解的情况下做到这一点？注意 - 需要素数因子的乘积(全部是功率统一).
这个答案解决了问题的后半部分 - 即是否可以在不分解数字的情况下计算素因数的乘积。这个答案表明这是可能的，并且显示了一种比简单的因式分解方法更有效的方法。然而，正如评论中所指出的，这种提出的方法仍然不如使用更先进的方法对数字进行因式分解那么有效。
令 k 为该数的立方根。
检查所有大小为 k 或更小的素数的数量，然后除掉我们找到的任何素数。
我们现在知道结果是大于 k 的素数的乘积，因此它必须是 1、单个素数或 2 个素数的乘积。（它不能有超过 2 个素数，因为 k 是该数的立方根。）
我们可以通过简单地测试这个数是否是完全平方数来判断它是否是2个素数的乘积。
假设我们已经预先计算了一个素数列表，这个结果允许我们以 O(n^(1/3) / log(n)) 的方式计算结果。
假设我们有号码 9409。
立方根是 21.1，所以我们首先检查是否能被 21 以下的素数整除。
他们都找不到结果，所以我们计算 sqrt 并找到 9409== 97**2。
这意味着答案是 97。
假设我们有数字 9797。
立方根是 21.4，所以我们检查是否能被 21 以下的素数整除。
他们都没有找到结果，所以我们计算 sqrt，发现 9797 不是完全平方数。
因此我们得出答案是 9797。（请注意，我们尚未确定计算此答案的因式分解。事实上，因式分解是 97*101。）