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

Question

我从标准输入中读取了一个正整数 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）和确定性上都以多项式方式完成，但他们的方法表明并非如此。