形式为 x^a + b 的数的素数分解，其中 x 是素数
Prime Factorization of numbers of form x^a + b where x is prime
我需要计算大数的质因数分解，大数是指范围 10^100。
我得到一个输入 a[0] <= 10^5（我已经使用筛法和其他优化计算出其主要因子）。之后我得到 a[1]、a[2]、a[3] 的一系列输入，都在 2 <= a[i] <= 10^5 范围内。我需要计算产品并获得新产品的因素。我有以下数学
设X为内存中的数据，X可以表示为：
X = (p[0]^c1)(p[1]^c2)(p[2]^c[3]) .... 其中 p [i] 是它的主要因素。
所以我将其保存为，
A[p[0]] = c1, A[p[1]] = c2.... 因为 p[i] <= 100000 这似乎工作得很好。
随着新数字的到来，我只是在 A 中添加新数字的素数次方。
所以这非常有效，而且速度也足够快。现在我正在考虑优化 space 并通过降低时间效率来补偿。
所以如果我可以将任何数字 P 表示为 x^a + b，其中 x 是素数。我可以分解它吗？ P 显然不适合内存但是 2 <= x, a, b <= 100000？或者是否有任何其他可能的方法可以节省 A 的 space？我可以接受比上述算法更慢的算法。
首先，您最好在纸上做一些数学运算（也许可以进行一些简化；我不知道...）。
那你需要用到一些arbitrary precision arithmetic (a.k.a. bignums or bigints) library. I recommend GMPlib but they are other ones.
另见 。
我不认为用质数表示 xa + b x 使分解更容易。
如今，因式分解百位数字并不是那么困难。一台有很多内核的好个人电脑 运行 一个好的二次筛可以在大约一天内因式分解大多数百位数字，尽管你应该知道百位数字大约在合理因式分解的极限台式电脑。查看 Jason Papadopoulos 的程序 msieve 以获得最先进的分解程序。
我需要计算大数的质因数分解，大数是指范围 10^100。
我得到一个输入 a[0] <= 10^5（我已经使用筛法和其他优化计算出其主要因子）。之后我得到 a[1]、a[2]、a[3] 的一系列输入，都在 2 <= a[i] <= 10^5 范围内。我需要计算产品并获得新产品的因素。我有以下数学
设X为内存中的数据，X可以表示为：
X = (p[0]^c1)(p[1]^c2)(p[2]^c[3]) .... 其中 p [i] 是它的主要因素。 所以我将其保存为，
A[p[0]] = c1, A[p[1]] = c2.... 因为 p[i] <= 100000 这似乎工作得很好。
随着新数字的到来，我只是在 A 中添加新数字的素数次方。
所以这非常有效，而且速度也足够快。现在我正在考虑优化 space 并通过降低时间效率来补偿。
所以如果我可以将任何数字 P 表示为 x^a + b，其中 x 是素数。我可以分解它吗？ P 显然不适合内存但是 2 <= x, a, b <= 100000？或者是否有任何其他可能的方法可以节省 A 的 space？我可以接受比上述算法更慢的算法。
首先，您最好在纸上做一些数学运算（也许可以进行一些简化；我不知道...）。
那你需要用到一些arbitrary precision arithmetic (a.k.a. bignums or bigints) library. I recommend GMPlib but they are other ones.
另见
我不认为用质数表示 xa + b x 使分解更容易。
如今，因式分解百位数字并不是那么困难。一台有很多内核的好个人电脑 运行 一个好的二次筛可以在大约一天内因式分解大多数百位数字，尽管你应该知道百位数字大约在合理因式分解的极限台式电脑。查看 Jason Papadopoulos 的程序 msieve 以获得最先进的分解程序。