给定一个数字 X ，计算该数字的质数 因子乘积的最有效方法是什么？ 有没有办法在没有实际分解的情况下做到这一点？ 注意-需要质因数的乘积(所有的幂为单位)。
最佳答案
这个答案解决了你问题的后半部分 - 即是否可以在不对数字进行因式分解的情况下计算质因数的乘积。这个答案表明这是可能的，并且显示了一种比朴素的因式分解方法更有效的方法。然而，正如评论中所指出的，这种提议的方法仍然不如使用更高级的方法分解数字有效。
令 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。)
关于algorithm - 数的质因数的乘积，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30154095/