10

这篇文章说:

每个素数都可以表示为 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 字节”呢?

4

4 回答 4

16

这篇文章有点误导:我们不能存储 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 万的限制。

于 2010-04-10T16:59:22.533 回答
11

您不需要存储 k 的每个值。如果要存储 100 万以下的质数,请使用 33,334 个字节——第一个字节对应 k=0,第二个字节对应 k=1,依此类推。然后,在每个字节中,使用 1 位表示“素数”或“复合数” " 对于 30k+1、30k+7 等。

于 2010-04-10T16:57:11.167 回答
4

这是一个位掩码——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 字节。)

于 2010-04-11T16:46:59.693 回答
0

从另一个角度来看,前 23,163,298 个素数可以被认为是可压缩的。它是每个间隙 <= 255 的最大素数数,即适合单个字节。

我在这里使用了这个事实,将素数缓存的内存占用减少了 8 倍,即number我不使用(8 个字节),而是只缓存素数之间的间隙,每个素数只使用 1 个字节。

于 2021-10-26T09:36:29.393 回答