素数分解

该库将计算任何 128 位无符号整数的所有素数因子。这些都是乘积后产生该数字的最小值。您可以使用附带的应用程序来实验。

内存效率

许多素数算法需要大量的内存，但访问主内存可能是一个缓慢的过程[^1]。虽然缓存可以提供一些帮助，但可能不足以满足需求。每次从主内存加载时，通常有足够的时间进行多达数百次计算。除非我们能找到一些工作来做，否则这些周期将会浪费。因此，即使有一些计算浪费，如果我们能最小化内存操作的数量，我们仍然可以实现一个高效的算法。

根据我的个人经验，任何需要存储大量数据的算法都会受到内存访问的限制，通常重新创建一些计算比从内存中加载它们要快。因此，不要保存那些可以轻松计算的值到内存中。

该代码的设计目标之一是在分解过程中最小化内存开销。只有最终的因子将被保存到内存中，并附带一个指数，而操作期间不会读取任何这些值。

[Latency Numbers Every Programmer Should Know]

素数生成器

我知道 生成器在 Rust 中尚未稳定。然而，在代码中我将使用 genawaiter，它基于 Rust 异步处理。使用生成器可以使我在运行时保持最小的状态，这比迭代器略好，因为迭代器需要重启其函数才能获得相同的结果。

该代码使用生成器来寻找潜在的素数候选者，其算法必须保证生成所有素数，但可能会产生一些假阳性。假阳性的成本是一个循环加上一次取模计算。请注意，任何非素数值从生成器中输出，其所有因子都将出现在已生成的数字中，因此它们永远不会出现在最终输出中。

我们希望这个生成器能够快速运行，并且对于素数给出合理的猜测。为此，我们使用了一个以30为基数的素数轮[^2]函数。在前一百万个数字中，它的命中率约为26.7%，考虑到其速度，这个命中率相当不错。考虑到误判正数并不那么昂贵，但误判负数是一个致命的缺陷。我完全预计命中率会在更高的数字中下降。

[^2]：更多信息请参阅维基百科上的轮分解文章。

分解性能

在旧系统（i7-6700）上，使用30辐轮

• 32位，随机数生成大约32毫秒，最坏情况300毫秒
• 64位，随机数生成大约1.4秒（± 1.1秒），最坏情况约20秒
• 完整的基准测试完成大约需要7分钟

在现代化系统（i7-12700）上，使用30辐轮

• 32位，随机数生成大约6.5微秒，最坏情况68微秒
• 64位，随机数生成大约140毫秒（[3 .. 340]毫秒）和最坏情况4.6秒
• 完整的基准测试完成不到3分钟

现代化系统（i7-12700）使用210辐素数轮

• 2..8位素数在12..34纳秒
• 9..16位素数在33..252纳秒
• 17..32位素数在0.25..57微秒，平均5.6微秒
• 33..64位素数在0.056..3704毫秒
• 65+位素数从3.65秒开始

上述数字取自包含的基准测试，您可以使用以下命令运行：cargo bench。请注意，运行完整的套件需要几分钟时间，在此期间您需要关闭所有其他应用程序，并让其独立运行，以便基准测试尽可能多的处理能力。