这是一个位掩码——30 个可能是素数的 8 个值中的每一个都有一个位,因此每 30 个数字有 8 个位。要将所有最高 10^6 的素数制成表格,因此需要 8*10^6/30 = 2666667 位 = 33334 字节。
要解释为什么这是一个好方法,您需要查看明显的替代方案。
一个更天真的方法就是使用位掩码。你需要一百万位,125000 字节。
您还可以存储素数本身的值。最多 1000000,这些值适合 20 位,并且有 78498 个素数,所以这给出了令人失望的 1569960 位(196245 字节)。
另一种方法——尽管对于查找素数不太有用——是存储每个素数和下一个素数之间的差异。在一百万以下,这适合 6 位(只要您记得此时素数都是奇数,因此您只需要存储偶数差,因此可以丢弃最低位),对于 470998 位 == 58874 字节. (你可以通过计算你必须跳多少 mod-30 插槽来减少一点。)
现在,除了 30 = 2*3*5 之外,30 并没有什么特别之处,所以这个查找实际上是在您开始之后引导您通过 Eratosthanes 筛网模式的位掩码表示。您可以改为使用 2*3*5*7 = 210,然后您必须考虑 +- 1、11、13、17、19、23、29、31、37、41、43、47、53、 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 48 个值。如果您使用 7 个 30 块来执行此操作,则需要 7*8=56 位,所以这是一个轻微的改进,但是呃……不值得麻烦。
因此,这是紧凑存储相当小的素数的更好技巧之一。
(PS 有趣的是,如果素数随机出现(但与实际出现的数字相同,最多可达 1000000),则存储在 1 到 10^6 之间的素数中的信息量约为每个数字 0.397 位。因此,在幼稚的信息论假设下,您可能会认为存储前一百万个素数的最佳方法是使用 1000000*0.397 位或 49609 字节。)