求第n个质数的最快方法：普通探测法与Willan公式对比及第1009个质数场景适用性探讨

让我直接把这个问题掰明白——Willan公式听起来是个“高大上”的闭合式质数表达式，但它完全不是为实用计算设计的，和普通探测法（尤其是优化后的版本）比起来，在实际效率上差了十万八千里。

先搞懂Willan公式的本质 #

Willan公式是一个能从数学上直接写出第n个质数的闭合式，它的形式大概是这样：
$$
p_n = 1 + \sum_{i=1}^{2n} \left\lfloor \left( \frac{n}{\sum_{j=1}^i \left\lfloor \cos^2\left( \frac{\pi (j-1)! + 1}{j} \right) \right\rfloor} \right)^{1/n} \right\rfloor
$$
但这个公式的核心问题在于：它的计算量是指数级爆炸的。里面嵌套了多层求和、阶乘、三角函数运算，光是外层求和的上限$2^n$，当n=1009时就是一个比宇宙中原子总数还大的数字——哪怕用当前最顶级的超级计算机，算到宇宙毁灭都出不来结果。它的价值仅仅是理论上的：证明质数可以用闭合式表达式表示，而非用来实际计算。

普通探测法的实用性（才是真正的“最快”） #

我们平时用的普通探测法，只要做些优化，效率就高得离谱：

• 优化试除法：判断一个数是否为质数时，只需要试除到它的平方根，同时跳过偶数、3的倍数这类明显非质数的数，大幅减少检测次数。
• 筛法（埃氏筛/欧拉筛）：如果需要找第n个质数，筛法是更好的选择——它能一次性生成某个上限内的所有质数，之后直接取第n个就行。比如第1009个质数是7927，我们只需要生成8000以内的质数，几毫秒就能搞定。

针对第1009个质数：选哪个？ #

答案绝对是普通探测法（筛法优先），完全没必要碰Willan公式：

• Willan公式计算第1009个质数的复杂度是$O(2^{1009})$，这是一个完全无法企及的计算量，没有任何实际可行性。
• 而用埃氏筛，只需要设定上限为8000，几行代码就能瞬间生成所有质数，直接索引到第1009个，效率碾压Willan公式。

总结 #

• Willan公式：理论意义＞实用价值，适合用来做数学证明，不适合实际计算质数。
• 实际求第n个质数，优化后的筛法或试除法才是最快的选择，尤其是当n在几千、几万甚至几十万这个量级时，都能轻松应对。

内容的提问来源于stack exchange，提问作者FariyaAchhab