10秒内计算出1亿素数表, 不输出

无心人

有兴趣做极大素数间隔么？ 我就测试过PII 400 1200亿/小时 计算到10^12 如果按你程序速度 可达到25000亿/小时 可在40000000小时内内计算到10^20的极大素数间隔

liangbch

n年前写过一个筛法求素数的程序，基本思想是这样的： 用数组arr( unsigned char arr[LEN])的每一个bit 表示 0 -- (LEN-1)*30+29 之间的数是否是素数，1表示是素数，0：表示是合数，具体的表示方法为： arr[i]的bit0:表示 30*i+1 arr[i]的bit1:表示 30*i+7 arr[i]的bit2:表示 30*i+11 arr[i]的bit3:表示 30*i+13 arr[i]的bit4:表示 30*i+17 arr[i]的bit5:表示 30*i+19 arr[i]的bit6:表示 30*i+23 arr[i]的bit7:表示 30*i+29 因为除了2，3，5以外，任何素数都可表示成上述8种形式之一，故上述表示法不会遗漏。 基本方法： 在筛之前，将所有bit都初始化为1,然后将表示合数的bit清0. 优点：每一个BYTE将表示30个数，采用分段筛法，在L2 cache 不变的情况下，每次能够筛的数比通常的方法增加了30倍，降低了内存读和写的次数，因此能够大大提高速度。 今晚试着重新实现一下该算法，看看速度如何。

无心人

我觉得并不比不压缩的字节表示快 也应该慢于位数组

tprime

目前最大素数间隔好像是1400多, 要破这个记录有点难。 除非将筛法改为针对prime gap 问题，并采用分布式计算

tprime

实际测试表明位压缩要快不少, 虽然操作耗时但CPU的带宽增加7倍（比位数组）

风云剑

位压缩能快很多，当然我认为原因是Cache，而不是算法。

mathe

这个题目本来就是如何优化对内存的访问问题。而且对于不同的机器（L1/L2cache，内存大小不同）得出的结果都会不同

shines

看了一下tprime的java代码，发现和我的非常接近，不过还是稍微有点区别 第一个，我们都用了类似的block，分段是按block来的，我称之为循环节，因为在做筛法的时候，筛2,3,5,7,11等的时候（2这里我们就不筛了），bit数组里是循环的，除了头几个字节要特殊处理以外。不过由于早几年我的CPU赛扬900的L2 Cache只有128KB，所以只做了3,5,7,11的block，循环中第一个开始筛的素数是13，差你的不少，因为现在CPU L2 Cache大了很多； 我们的bit数组其实是一样的，你的代码中MOVE＝5，让我纳闷了很久，后来才想起来，可能Java的Char是双字节的，其实在C/C++里，MOVE应该＝4，也是一个字节表示16数； 实际开始筛的时候，你的代码好像是做了6*K+1, 6*K+5的筛，而我做的是30*K+1, 30*K+7, 30*K+11, 30*K+13, 30*K+17, 30*K+19, 30*K+23, 30*K+29的筛，如果你也做30*K＋N的筛应该可以更快。我的代码又长又丑，写得不是很好，也有很多改进的地方，不好意思公开。 对于liangbch大哥提的一个字节表示30个数，看起来不错，不知道实现起来怎么样

tprime

我在java版本上尝试过模30，测试效果不好, 代码中你注意到没有, 那段代码被我注了 相反在C++中速度提升20%, 更大的模如210, 2310, 30030是可以尝试的 估计性能提升不大。block 应不超过L2 的 2/3 性能最好

liangbch

我的程序完成了,源代码见附件。在我的电脑（PIV2.6G，768M RAM）筛2-2^31,需5.6秒（9楼的程序需要30秒）筛2-10亿之间的所有素数，需要2.5秒。 shine可否测试一下，比你的程序如何。