algorithm - 启发式 - N 是质数吗？

Question

我从 stdin 中读取了一个正整数 N，然后我试图确定 N 是否是素数。

我知道我可以将 N 除以所有正数直到 sqrt(N)，但这很耗时，而且我的算法有时会给出误报，所以我正在寻找一种启发式方法来解决这个问题。

我记得我去年在拼贴画中学习了一种算法，它会选择一个数字，然后检查 N 是否可以被该数字(或其因子)整除，如果不能，那么它可以判断 N 是素数，但它会大约有 1/40 的时间错误地将其识别为素数。

有人认识我说的这个算法吗？指向它的链接会非常有帮助。

Answer 1

好吧，有一些概率算法，一些在 wikipedia page 中有描述。 ，您很可能在谈论 Miller-Rabin Fermat Primality Test

请注意，自 2002 年以来，实际上有一种 O(log(n)^6) 确定性方法来确定一个数是否为质数 - 称为 AKS (在其开发者之后) ¹

---

这是一个有趣的问题 - 许多人认为素数测试不能同时以输入大小的多项式(即 n 中的对数)和确定性的方式完成，但他们的方法表明并非如此。