haskell - 二次筛和 n 次幂

Question

我根据维基百科页面上指定的基本算法在 Haskell 中实现了二次筛。它适用于大多数整数，但它无法找到 n 次幂的数字 N 的因式分解。对于偶数次幂(平方)，算法循环，对于奇数次幂，我找到了几个平方模 N 的平滑数(我已经测试并证实了这一点)，但是每个衍生的平方同余(也经过测试和确认)只导致一个微不足道的因素。

我有理由确信我实现了维基百科算法。那个版本的算法是否有问题阻止它处理 n 次幂，或者我的算法中是否有错误？

出于某种原因，stackoverflow 在格式化我的代码时遇到问题，所以你去:http://pastebin.com/miUxHKCh

Answer 1

据我所知，二次筛法并不是为了确定一个数字而设计的。相反，它旨在在典型情况下通常分解一个数字。

例如，至少在今天，维基百科条目将其描述为“没有对数优化或素数幂的标准二次筛”。所以它明确没有考虑素数。

此外，据我所知，接近质数幂的数字的因式分解在更有效的算法变体中也不能很好地工作。

因此，错误不在于您的代码，而在于算法通常的呈现方式(它掩盖了诸如它是否始终有效或只是通常有效等问题:-))