我的任务是找到一个数字的所有质因数...
我需要编写一个函数，它接受一个数字并告诉我这个数字的所有主要因素。例如：
- n=350 质因数：2 5 5 7
（我将 0 到 18446744073709551615 范围内的数字传递给函数 - 最大数字是适合 64 位无符号长整数的最大数字。）
问问题
1854 次
1 回答
2
这是一个难题，也是所有量子计算机研究的主要原因之一。看看Shor 的算法。没有优化的简单暴力破解大约需要 1000 年，尽管在这种特定情况下（64 位整数），您应该能够将运行时间减少到几分钟。
假设您有一个（至多）一个大素因数的小例子，您可以通过从 2 开始计数并尝试每个数字（如果有效，则多次尝试；12 将是 2、2 和 3）来显着加快速度例子）。找到一个因子后，将目标数减少该因子并测试新目标是否为素数。
为了进一步加快速度，您可以跨多个线程进行处理，每个线程负责一系列除数。您可以在一个或多个线程上运行素数测试器，为测试线程提供素数，因此您只尝试除以素数。
如果您认为提供该值的人试图欺骗，您甚至可以从范围的顶部向下搜索，尽管素数的密度在低端高得多，这可能无济于事。
但是，要记住的主要事情是，除了 X 本身之外，X 的最大可能因子是 X 的平方根。每次找到一个因子时，最大可能的剩余因子显着减小。
于 2010-11-22T14:24:38.867 回答