2

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

我有理由确定我已经实现了 Wikipedia 算法。那个版本的算法是否存在问题，阻止它处理n次幂，或者我的算法中是否存在错误？

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

4

1 回答 1

3

据我了解，二次筛的设计并不是为了确定一个数字。相反，它的设计目的是在典型情况下通常考虑一个数字。

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

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

因此，错误不在您的代码中，而在于算法通常呈现的方式（它掩盖了诸如它是否总是有效或通常有效等问题：-)）

于 2015-03-12T21:13:11.837 回答