这篇文章说：
每个素数都可以表示为
30k±1,30k±7,30k±11, 或30k±13对于某些k。这意味着我们可以使用每 30 个数字中的 8 位来存储所有素数；一百万个素数可以压缩到 33,334 字节
“这意味着我们可以使用每 30 个数字中的 8 位来存储所有素数”
这个“每 30 个数字 8 位”将用于k，对吗？但每个k值不一定只占用一位。不应该是八个 k 值吗？
“一百万个素数可以压缩到 33,334 字节”
我不确定这是怎么回事。
我们需要指出两件事：
k的值（可以任意大）
来自八个州之一的州(-13,-11,-7,-1,1,7,11,13)
我没有关注“33,334 字节”是如何得出的，但我可以说一件事：随着质数的值越来越大，我们将需要更多空间来存储k的值。
那么我们如何将其修复为“33,334 字节”呢？
这篇文章有点误导：我们不能存储 100 万个素数，但我们可以存储 100 万以下的所有素数。
k 的值来自它在列表中的位置。对于这 8 个排列（-13,-11..,11,13）中的每一个，我们只需要 1 位
换句话说，我们将使用 8 位来存储 k=0，8 位来存储 k=1，8 位来存储 k=2，等等。通过让这些顺序跟随，我们不需要指定值每 8 位的 k - 它只是前 8 位 + 1 的值。
由于 1,000,000 / 30 = 33,333 1/3，我们可以存储这 8 位序列中的 33,334 个来表示低于 100 万的值是质数，因为我们涵盖了 k 可以具有的所有值，而 30k-13 不超过 100 万的限制。
您不需要存储 k 的每个值。如果要存储 100 万以下的质数，请使用 33,334 个字节——第一个字节对应 k=0，第二个字节对应 k=1，依此类推。然后，在每个字节中，使用 1 位表示“素数”或“复合数” " 对于 30k+1、30k+7 等。
这是一个位掩码——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 字节。）
从另一个角度来看，前 23,163,298 个素数可以被认为是可压缩的。它是每个间隙 <= 255 的最大素数数，即适合单个字节。
我在这里使用了这个事实，将素数缓存的内存占用减少了 8 倍，即number我不使用（8 个字节），而是只缓存素数之间的间隙，每个素数只使用 1 个字节。