zhec.moe

发现一个新的大素数需要多久？

省流

使用一颗普通的 8 线程 CPU 在 PrimeGrid 上计算 GFN-16 任务，可以期望在 35 天左右发现一个 57 万位的大素数。

GIMPS 和 PrimeGrid

在找大素数这方面，GIMPS 无疑是最知名的分布式计算计划，它集中所有计算资源寻找形如 $$2^p-1$$ 的梅森素数。目前人类已知的第一大（$2^{136279841} - 1$，$41024320$ 位）至第五大的素数都是由 GIMPS 找到的。但是随着位数的增加，一方面素性判断的计算时间逐渐变长，另一方面素数出现的频率也逐渐下降。过去十年间，GIMPS 一共只发现了四个梅森素数。考虑到它全站的算力目前在 5000 TFLOP/s 左右，用个人计算机那微不足道的算力，想找到一个新的梅森素数实在希望渺茫。

相比之下，PrimeGrid 搜索的素数类型比 GIMPS 更丰富，其中有些类型的素数（相对来说）极其容易找到。仅 2025 年一年，PrimeGrid 上就找到了 3419 个素数，这个爆率看着就大多了。PrimeGrid 包含十几个子计划，每个子计划搜索一类素数。各个子计划的候选素数位数从五十多万到四千多万不等，目前位数最短的子计划是 Generalized Fermat Prime Search (n=16) (GFN-16) 和 Proth Prime Search Extended (PPSE)。在 PrimeGrid 上搜索最近发现的素数，绝大多数都属于这两类素数。

广义费马数（Generalized Fermat Number, GFN）是形如 $$b^{2^n}+1$$ 的数，如果它是素数则成为广义费马素数。PrimeGrid 上有一系列从 $n=16$ 到 $n=23$ 的子计划。其中， $n=16$ 的子计划按 $b$ 从小到大搜索 $b^{65536}+1$。目前它的候选素数在 57 万位左右，是所有 PrimeGrid 子计划中最小的。

$n=23$ 的任务旨在反超 GIMPS 的最大素数纪录，它的候选素数超过 4300 万位，正好比 4100 万位的已知最大素数稍大一些。有趣的是，由于发现素数的概率真的很小，这个子计划叫做“Do You Feel Lucky?”。

Proth 数是形如 $$k \times 2^{n}+1$$ 的数，如果它是素数则成为 Proth 素数。搜索 Proth 素数的子计划有两个：Proth Prime Search (PPS) 和 Proth Prime Search Extended (PPSE)。它们俩的区别在于 $k$ 的范围。PPS 搜索 $k < 1200$，而 PPSE 扩展到 $1200 < k < 10000$。不过 PPSE 的 $n$ 比 PPS 小得多，因此候选素数的位数也更小，目前在 71 万位左右。

计算期望时间

在 PrimeGrid 的 Task status page 里，可以找到 GFN Tasks Completed Each Day - by year 和 LLR Tasks Completed Each Day - by year 的统计图：

这两张图里最关键的数据是“GFN-16 - Avg - 39.48k”和“PPSE - Avg - 31.10k”。这表示在 2026 年 5 月 21 日之前的一年中，PrimeGrid 每天平均完成 39480 个 GFN-16 任务和 31100 个 PPSE 任务。

那么这一年里发现了多少素数呢？在 Primes by Project 页面查询 GFN65536 和 PPSE 两个子计划发现的素数，在 2025-05-21 到 2026-05-21 发现的分别有 869 和 475 个。

因此，过去一年中每个 GFN-16 任务找到素数的概率是 $$\frac{869}{39480 \times 365} = 6.03 \times 10^{-5} \approx \frac{1}{16583}$$

而每个 PPSE 任务找到素数的概率是 $$\frac{475}{31100 \times 365} = 4.18 \times 10^{-5} \approx \frac{1}{23898}$$

在 Task status page 还可以查询到每类任务的平均执行时间：

可以看到，这一年中 GFN-16 任务的平均 CPU 执行时间是 0.41097 小时，大概 24 分钟。PPSE 任务则是 0.66758 小时（40 分钟）。

那么找到一个 GFN-16 素数的期望计算时间就是 $$ \frac{0.41097 \times 16583}{24} = 283.96$$ 天，而找到一个 PPSE 素数的期望计算时间是 $$\frac{0.66758 \times 23898}{24} = 664.74$$ 天。

不过这个结果还没有考虑到 CPU 的多线程并行。假如使用一颗 8 线程 CPU 进行计算，找到一个素数的期望时间会进一步缩短至 35 天（GFN-16）和 83 天（PPSE）。当然，达到期望时间不代表一定就能找到一个，时间没到也有可能提前发现，这就全凭运气了。

超大素数

超过一百万位的素数被称为超大素数（Megaprime）。要想找到一个超大素数，PrimeGrid 上最容易的子计划是 GFN-17 （因此又称 GFN-17-Mega）和 PPS，它们的候选素数目前分别达到了 113 万位和 137 万位。根据上文的计算方法，可以算出找到它们的期望时间分别是 208 天和 343 天，难度陡然增大。