存入前N个素数，所需存储量为多少

wsc810

大家估算一下，假如要建立一个目前世界最大素数库，最大素数暂定为第47个梅森素数，要把这么多的素数存入计算机，需要的最少存储量为多少字节？

liangbch

采用增量编码存储，采用最简单的编码，存储前n个素数，约需要n个字节。不过缺点是只能顺序检索。存储方法如下。

1. 定义Pi表示第i个素数，如p1=2,p2=3. 前2个素数不在这个表格中存储。
2. 定义tab[i]= (p[i]-p[i-1])/2, 例如： tab[3]=(5-3)/2=1, tab[4]=(7-5)/2=1, tab[3]=(11-7)/2=2等，这个表格的每个元素只需要1字节。
   如果 (p[i]-p[i-1])>=512, 这种情况很少见，则使用3个字节存储，第一个字节是0，第2，3字节表示(p[i]-p[i-1])/2。

总体说来，存储前n个素数，约仅需n个字节多一点的空间。如果采用哈夫曼编码，则所需空间可大大压缩。

KeyTo9_Fans

$2#$ liangbch

“存储前$n$个素数，约仅需$n$个字节多一点的空间。”

如果采用增量编码存储，这个结论仅在$n\leq 10^256$的时候成立。

当$n\leq 10^65536$时，需要$2n$字节；

当$n\leq 10^16777216$时，需要$3n$字节；

……

依次类推，得：

当$n\leq 10^{256^k}$时，需要$kn$字节；

也就是说，存储前$n$个素数，需要$O(n\log\log n)$字节。

mathtime

为何不把47个梅森素数列出,大家可以详细讨论一下。
在不同的环境下需要的字节数有区别。

zgg___

恩，如果你想建立一个表，这个表罗列出从2到第47个梅森素数的所有素数。那么即使你动用全宇宙所有的粒子，也无法储存储存这个表；不管你用现有的什么压缩和表达方式，这个无法存储的事实也无法改变；即使是针对这个表的九牛一毛也是一样的结果。这个表（即使是压缩后的，即使是其九牛一毛的一小部分）所蕴含的信息，也不可能全部被搜索一遍。换一种说法，从这个表的第一位开始，如果用一个只有一位寄存器，它的状态将这个表的01状态历遍全部一次，那么所需要的能量，在热力学定律的基础上，将远远超过全宇宙的能量。也就是说这个任务是无法完成的，除非拥有传说中的所谓的超物质和超能量。呵呵。

liangbch

几个问题，

1. 你这个 $n<10^256$是这么来的。
2. 我的方法并不是$n<10^65536$,需要2n字节,对于所有很大的素数，仅当相邻素数的间隔很大时，才需要2个字节。比如，哪怕是1亿位的的孪生素数，存储后一个也只需要1字节。
3. 我的结论是结合现实情况给出的，不讨论和现实情况相差很大的极端情况，你所说的n=$10^256$,n以内的素数将超过1.696462819934577451762222339518e+253个，若硬盘技术极度发达，可使得每个质子存储1字节数据，则银河系的质子数为 2*10^30 * 10^12/ 1.67*10^-27 =10^69,造一个能存储这么多素数的硬盘也远远不够。

注：太阳的质量为10^30千克，银河系的质量为太阳质量的1万亿倍，见http://www.zxxk.com/ArticleInfo.aspx?InfoID=159761. 质子的质量为1.67×10^-27千克。



说正经的，查了一下相关资料，发现，
仅当 $p_i>=304599508537$,$p_i$和下一个素数的间隔才会超过512,之后相邻素数的间隔超过512的概率也非常少。按照我的方法，即使对于很大的连续的素数序列，仅当某两个素数的间隔超过512时，才需要多个字节，否则依然只需要一个1节。如果某个相邻素数的间隔超过65536，那个这个素数的将非常大，目前尚不清楚。仅以http://www.trnicely.net/gaps/gaplist.html#MainTable 给出的数据，仅当$p_i>=1425172824437699411$，相邻素数的间隔才会超过1476. 根据素数定理，这个1425172824437699411大概是第34094370926914147个素数，如果存储这个素数以内的素数，每个素数使用1字节存储，需要34094T。需要17000块2T硬盘，以每块硬盘600元计算，尚需花费1020万元。

风云剑

这个问题比较狠啊，M47超过一千万十进制位了。

云梦

看来你的这个建议不可能实现的。
不超过第47个梅森素数的素数将有1.0590175682245286556122055501765 E12978181个。
这些素数十进制位数将达1.3744130117556751456876232062135 E12978188位。
1BB=1024^9字节，如果1BB是一个原子。(原子直径10^-8cm)
1立方公里将有10^39原子。
宇宙直径120亿光年，合1.463279617158414336* 10^69立方公里，
将可包容1.463279617158414336 E108个原子。
因此我们的宇宙也只能装下1.811452426 E135BB个字节。你需要几个宇宙呢？

gxqcn

存储的形式很多，有纸质的，有电子的。
存储的方式很多，有直接的，有压缩的。
压缩的，又分通用压缩的，或针对素数问题特殊处理的。
查阅的方式，可分直接的，或间接的（比如记录的是相邻素数间隔时）。

其实，除了纸质形式外，都需要借助计算机处理，
那为什么非要是个数据包，而不是个程序？
用一个能判定大素数的程序，并提供 NextPrime 功能，则一切都好办了，
只是非常大的整数素性判定，可能需要非常非常多的机时，但毕竟理论上可以“提供”出结果，
是否可算满足了楼主的要求？
如果这样的话，所需的存储量也许仅是兆字节级别足矣。

云梦

建立素数库目的是便于检索，即使有了这个大素数库，检索还是需要程序才能实现。因此建立素数库没有实际意义。这只是因为目前还没有更好更快的素数判定程序。
一个程序只需几兆字节就足够了，等于拥有了这个的素数库。