以编程方式分解大量数字

Question

好吧，我有一个巨大的数字f。实际上，这个数字只有 100 多位数字长。我知道这些因子的大小大致相同。

如果我的资源和时间有限，我应该使用什么语言和算法？我在限制时间内包括了编写算法的时间长度。

想法？

编辑：我所说的有限是指在尽可能短的时间内。

Answer 1

最先进的素因数分解算法是二次筛及其变体。对于大于 100 位的数字，数字筛 变得更加高效。

此处有它的开源实现。它能够在 2.2 GHz 上仅用 4 小时将 100 位数字分解为两个大致相等的素数AMD Althon。

这就是算法和示例实现。这可能足以为您提供想法或帮助您开始。

Answer 2

这听起来像是云计算的一个很好的练习（也可能是一个罕见的好例子）。这应该很容易运行并行处理。将因素池划分到每个流程中。

像这样的东西可能会有所帮助： http://blog.controlgroup.com/2010/10/13/hadoop-and-amazon-elastic-mapreduce-analyzing-log-files/ 更多详细信息，请访问 http://en.wikipedia.org/wiki/Apache_Hadoop#Hadoop_on_Amazon_EC2.2FS3_services 。

（在过去的一个月中，我观看了一个很好的视频演示，演示了类似于我在这里建议的内容的穹顶 - 但当然，现在我找不到链接。）

特别是如果您不需要以编程方式执行此操作，看看http://www.alpertron.com.ar/ECM.HTM . （链接自 http://en.wikipedia.org/wiki/Quadratic_sieve。）请注意第一个链接上“在多台机器中分解数字”下的注释。 （由于源代码可用，您也可以使用 Hadoop 等以编程分布式方式运行它。）

Answer 3

while (x < Number) {
    if ((Number % x) == 0 ) { 
        cout << x << "*" << Number/x << endl;
        ++x;
    }  
    else ++x;
}