6

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

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

想法？

编辑：有限，我的意思是在尽可能少的时间内。

4

3 回答 3

8

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

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

所以有算法和示例实现。这可能足以给你一些想法或让你开始。

于 2012-01-15T06:50:18.457 回答
1

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

这样的事情可能会有所帮助： 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 等以编程方式分布式方式运行它。）

于 2012-01-15T06:40:06.763 回答
-2 
while (x < Number) {
    if ((Number % x) == 0 ) { 
        cout << x << "*" << Number/x << endl;
        ++x;
    }  
    else ++x;
}
于 2012-01-15T06:43:34.190 回答