2

我试图找出10 ^ 18数量级的所有数字因子......但是有时间限制会产生问题。我所做的是使用 Eratosthenes 的 Sieve 来查找因子，然后存储因子，但速度很慢......

4

3 回答 3

4

如果空间不是问题，您可以存储最多 10^9 的素数列表（列表可供下载）并使用它来分解最多 10^18 的任何数字。您还可以使用因式分解算法（如 pollard 的 rho 或其他算法）。

于 2012-09-03T16:49:10.290 回答
1

我真的建议阅读有关此整数分解的 Wiki 文章：http ://en.wikipedia.org/wiki/Integer_factorization

通用因式分解方法很慢。但是，可以尝试使用一些特殊用途的方法。

于 2012-09-03T16:49:19.883 回答
0

将素数列表 p<=10^9 存储到因数 N<=10^18 的想法的问题在于，对于任何特定的 N，您仍然需要遍历素数 p<=sqrt(N) 并检查是否 N%p==0。这不是做生意的最快方式。

从你的问题中不清楚你是想分解一堆 10^18 的数字，还是想分解所有数字 N<=10^18。第一种情况是可行的，具体取决于您要考虑多少 N 以及需要多快。第二种情况，将所有数字分解为 N<=10^18，是不可行的，因为这将需要超过 10^18 次操作（每个要分解的数字至少一个）。考虑到计算机每秒可以执行大约 10^9 次操作，而一年中大约有 10^7 秒，那么您会考虑很长时间。

如果您只想将一堆数字 N 分解为 10^18 的数量级，那么有很多方法可以做到这一点。“最佳”方式取决于特定数字的属性。例如，平均而言，10^18 左右的随机整数比 10^9 阶的两个素数乘积的整数更容易因式分解，因为在转向更复杂的算法之前，可以通过试除法消除小因素。这更像是一个计算数论问题而不是编程问题。如果这是您的问题，我向mersenneforum.org 的 Factoring 部分推荐。

如果您想要一个快速而肮脏的解决方案，而且速度不会慢得离谱，那么不要重新发明轮子。尝试例如 GMP-ECM 或查看 PARI/GP 是否可以解决您的问题。

于 2012-09-20T00:59:59.237 回答