需要考虑的是以下函数，该函数可用于（相对快速）将 64 位无符号整数分解为其素数。请注意，因式分解不是概率的（即，它是精确的）。在现代硬件上，该算法已经足够快，可以在几秒钟内找到一个数是素数或几乎没有非常大的因数。

问题：可以对所提出的算法进行任何改进，同时保持单线程，以便它可以更快地分解（任意）非常大的无符号 64 位整数，最好不使用概率方法（例如 Miller-Rabin）确定素数？

谢谢

编辑：我添加了更多评论。通过引用传入向量的原因是允许在调用之间重用向量并避免动态分配。向量没有在函数中清空的原因是允许将当前“num's”因子附加到向量中已经存在的因子的奇怪要求。

函数本身并不漂亮，可以重构，但问题是如何让算法更快。所以，请不要提出关于如何使函数更漂亮、更易读或 C++ish 的建议。那是儿戏。改进这个算法，使其能够更快地找到（证明）因子是困难的部分。

更新：到目前为止， Potatoswatter有一些出色的解决方案，请务必在底部附近查看他的 MMX 解决方案。

这是我目前拥有的代码，但是我已经在 DrJava 中运行了几分钟，但它没有返回任何结果。我猜有大约一百万种方法可以优化我的代码；谁能给我一些提示？

今天尝试解决一些编程问题，这给我带来了一些麻烦。

非常感谢 ：）

我想知道是否可以通过在 C# 中使用模数来找到一个数字的最大素数。换句话说，如果i % x == 0那时我们可以打破一个for循环或类似的东西，其中x等于所有低于我们i值的自然数。

我将如何指定all natural numbers below our i value等于我们的 x 变量？如果你知道我在说什么，为每个整数写出条件会变得有点乏味。

顺便说一句，我确信在 C# 中有一种更简单的方法可以做到这一点，所以如果你有想法，请告诉我，但我也想尝试以这种方式解决它，只是为了看看如果我能用我的初学者知识做到这一点。

如果你想看看我到目前为止有什么，这是我当前的代码：

所以，我正在学习 Haskell，并且经常陷入与类型/类型类相关的错误。一些非常明显的愚蠢错误，还有一些让我觉得 haskell 不适合我。无论如何，我有这段代码......

（一些背景：pfactors 函数应该接受一个数字并返回一个素数列表，这些素数是给定数字的素数。primes是一个无限的素数列表）

这给了我这个错误：

现在我明白这是p < (sqrt n)零件的问题，因为它是唯一与Floating. 如果我将其更改为p < n一切正常，我会得到正确的答案。但我真的很想检查平方根，那我该怎么做呢？

顺便说一句，这不是作业，如果感觉像，这是我在 projecteuler.net 上解决第 47 个问题的尝试

谢谢你的帮助。

而且，请不要给我解决上述项目欧拉问题的方法，我想尽可能自己做:)。谢谢。

我正在寻找一种实现或清晰的算法，以在 python、伪代码或其他任何可读性良好的东西中获取N的主要因素。有一些要求/限制：

• N介于 1 到 ~20 位之间
• 没有预先计算的查找表，但是记忆很好
• 不需要经过数学证明（例如，如果需要可以依赖哥德巴赫猜想）
• 不需要精确，如果需要可以是概率/确定性

我需要一个快速的素数分解算法，不仅是为了它本身，而且是为了在许多其他算法中使用，比如计算 Euler phi(n)。

我已经尝试过来自 Wikipedia 等的其他算法，但要么我无法理解它们（ECM），要么我无法从该算法（Pollard-Brent）创建一个有效的实现。

我对 Pollard-Brent 算法真的很感兴趣，所以任何关于它的更多信息/实现都会非常好。

谢谢！

编辑

在搞砸了一点之后，我创建了一个非常快速的素数/分解模块。它结合了优化的试除法算法、Pollard-Brent 算法、米勒-拉宾素数测试和我在互联网上找到的最快的素数筛。gcd 是常规 Euclid 的 GCD 实现（二进制 Euclid 的 GCD比常规的慢得多）。

赏金

哦，快乐，可以获得赏金！但是我怎样才能赢呢？

• 在我的模块中查找优化或错误。
• 提供替代/更好的算法/实现。

最完整/最具建设性的答案将获得赏金。

最后是模块本身：

我一直在尝试在 Scala中解决 3 中的项目欧拉数，这就是我到目前为止所得到的：

我认为这会起作用，但我被困在工作中（在缓慢的构建过程中利用时间）并且只有 SimplyScala 服务——它正在超时（我会在家里检查它）。

但由于这是我写的任何长度的 Scala 的第一部分，我想我会问，我犯了哪些可怕的罪行？我的解决方案是多么不理想？我践踏了哪些约定？

谢谢！

我正在解决欧拉项目3：

这是我生成答案的代码。但是我需要一个整数类型来保存600851475143。当我在 Mac 上的 GCC 上编译它时，我得到：

我预计long long可以轻松持有这个数字。我也试过让它不签名。为什么我的代码没有这么小的数字，我该怎么做才能让它工作？

我试图在java中实现一个简单的算法来查找参数传递的整数的所有素数因子：

有趣的是，如果我将 81 作为 n 传递，结果将是：3、3、3、3、3、3、3、3 而应该是：3、3、3、3 (3^4=81)

我正在尽我所能改进这个有趣的算法。

现在，我有这个：

那么有什么想法吗？

谢谢！

编辑：我实现了 Ben 的算法，感谢大家的帮助！

对于家庭作业，我需要逻辑来找到从 1 到 1000 的一系列数字，它们正好有七个除数。

（理想情况下，可以轻松修改代码以生成素数。）