Haskell库中是否有一个整数分解函数？

Question

我发现一些实现整数因式分解函数的库。最好是一些流行库中快速的实现，避免重复造轮子。

有这样的库吗？

- s9gf4ult

Answer 1

快速谷歌搜索显示Daniel Fischer的arithmoi包。

- Satvik

---

Arithmoi很棒。它不仅包含许多数论工具，而且还正确地实现了它们，并且接近GMP的速度。 - ertes

它没有覆盖测试，对我来说不太好... - s9gf4ult

@s9gf4ult：在提问时给出限制条件会更有帮助，而不是在回答后再加上。 - President James K. Polk

它有一个相当复杂的“认证”基础设施。如果您能更清楚地表明您想要什么，这可能会有所帮助。 - applicative

Answer 2

请查看primes中的primeFactors。例如，它可以快速分解104729 * 104723。

- Petr

---

请注意，104729 * 104723 可以通过简单的平方根测试和一些线性探测来推导出。更好的分解试金石测试将涉及距离较远但不太接近 1 的质数。考虑 104729 * 88801。 - recursion.ninja