c++ - 除数算法

Question

我得到了一个整数列表(最多 1000)，它们乘以给定的整数 n。

我需要在整数 n 的所有约数中找到最高的幂。

例如:4,7,8 乘以 224，然后最高次方为 5，因为 224=2^2*7*2^3=2^5*7。

问题是，1000 个整数可以大到 2^64，因此 n 非常大。

解决这个问题的好算法是什么？

Answer 1

很难。我会先开始检查小素数(在你的例子中:4、7、8。乘积有一个因子 2^5。你除以 2 的幂，剩下 1、7、1。然后你对 3 做同样的事情, 5, 7 等直到 X)。

现在您需要找到一个更大的素数 p > X，其幂次高于您找到的最高素数。花大量时间寻找只出现一次的主要因素似乎很浪费。您需要作为多个数因数的素数。计算每对数字的 gcd 并查看这些数字的质因数。有很多细节需要解决，这就是为什么我从“困难”开始。

最坏的情况是您无法轻易找到任何出现两次的素数，因此您需要检查每个数字是否包含素数的平方作为因子。

举个例子:你检查了 1000 以内的因数，你发现素数的最高次方是 83^3。所以现在你需要找到一个更大的素数，它是四次方或者证明没有。计算成对的 gcd(最大公约数)。一个大素数可以是来自四个不同数字的这些 gcd 的倍数的除数，或者 p 可以是三个 gcd 的因数，p^2 是一个数的因数等。

阐明原理:假设你有两个巨大的数字x和y，你想知道哪个是素数的最大幂来整除xy。你可以分解 x 和 y 然后从那里开始。如果它们都是质数或两个大质数的乘积，比如 x = p 或 pq，并且 y = r 或 rs，这需要很长时间。

现在计算 x 和 y 的 gcd。如果最大公约数为 z > 1，则 z 是 x 和 y 的因数，因此 z^2 是 xy 的因数。如果最大公约数为 1，则 x 和 y 没有公因数。因为我们不需要非平方因子，所以我们寻找平方和更高的因子。为此，您只需要除以 x^(1/3) 或 y^(1/3) 的因数。