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

风云剑

Pi(X)的话不能输出啊，他那个可以输出的。

shines

不是的, 在这一点上GxQcn的素数程序是做得很不错的, 比较合理, 从使用的角度, 有效率且方便.

当你只想知道个数时, 他只用PI(X)函数计算, 如果你要输出的话, 他才用筛选法计算.

编程时的具体实现过程, 我猜想, 他计算某范围的素数个数的时候, 一直用的PI(X)函数, 而不比去统计筛法里分段的素数个数, 虽然统计的话也不是很耗时, 但是毕竟时间会少一点, 而且界面上素数个数, PI(X)是符合要求的.

当你勾选了输出到EditBox或文件的时候, 才用筛法来计算, 并保留所有的bit数组(或者任何标记数组), 但不输出, 等所有的分段计算完成, 在一次性的输出EditBox或文件里面. 这是因为分段筛法的时候没必要去输出, 那样可能会变慢一点, 尤其是输出到EditBox的时候, 数据一多, 慢得出奇, 如果是输出到文件还能接受.

他的程序的output 栏显示的时间是计算时间(筛法筛的时间) , 而不是输出时间, 这里有点歧义, 而真正的的输出时间是输出到EditBox或者写数据到文件所花的时间, 这是不显示的. 为什么要把输出单独拿出来? 因为这样才能有可比性, 否则不同的算法可能会因为输出效率影响而不能很好体现其真正的效率. 还有因为默认的 EditBox 不支持虚拟显示技术, 数据一多, 就慢如蜗牛. 以上可以从他的软件观察得到.

为什么可以这么做? 因为计算 2^30 内的素数所用的bit数组内存大小对现在的系统是可以接受的, 如果要计算更大范围内的素数, 而内存无法承受的时候, 再对整个范围分N个大段, 计算->输出->计算->输出->计算->输出.....

gxqcn

楼上的分析比较深入，但还略有些误解，比如“他的程序的output 栏显示的时间是计算时间(筛法筛的时间) , 而不是输出时间”

在我的 PrimeNumber.exe 主界面中共有三处计时输出，这里披露一些细节：

PrimeNumber 界面

一、右上的那个，也即永远会显示的那个，是仅统计用户设定范围内素数数目的耗时。紧接着还要迅速精确计算出“若要输出的话，将有多少个字节，多少行？”（鼠标移到Output栏中会提示），为了加快这段过程的计算，程序预存了 n=10^r 系列的 pi(n) 值（少量的常量）；可能有人认为这是作弊，其实一切是为了用户体验为导向；

二、当钩选了输出到屏幕或[和]存文件时，还会有接下来的两个。鼠标移至左边那个大输出窗口上时，动态显示的确实是筛选素数的耗时。但程序一启动就自动将小范围内的素数给计算好了（为了给前面的计算pi(n)加速），所以在小范围内时仅仅是个memcpy动作而已（同样的，一切以用户体验为导向）；

三、至于Output标题栏上显示的耗时，则是内部将全部素数由数字转化为字串的耗时，不包括接下来的I/O耗时。

无心人

0.61s
还是可以超越的
目前俺在400M PII上的速度是3s

可惜程序找不到了，发CSDN上有一个
不知道在哪里！

tprime

gxqcn的程序很好用, 输入有一点不大方便,  
比如上次输入beg, end
下次重新输入的beg必需小于上次的end, 否则弹出的对话框比较讨厌
（期待更新, 用户点击计算的时候可以验证beg <= end）

无心人

我想到个好技巧
筛的时候从后往前筛
假设ecx表示地址偏移
只要ecx小于0就表示结束

liangbch

原帖由 无心人 于 2008-3-17 15:06 发表
我觉得并不比不压缩的字节表示快
也应该慢于位数组

  筛法求素数主要算法是：
   1.预置一个数组，初始化为所有的数都是合数，然后筛去素数的倍数。
   2.关于数组的表示方法，我知道的有BYTE数组（每个BYTE表示一个数),bit数组（每个bit表示一个数，若要筛n个数

，只需要n/8字节），压缩的bit数组3种.对于压缩的bit数组,每个bit只对应一些可能的素数，对一些明显不是素数的则

没有对应的bit，如bit值对应形为2K+1的或者形为30K+(1,7,11,13,17,19,23,29)的数，后者对于n个数只需要n/30个字

节。这使得内存写的次数大大缩小，可明显的提升筛的速度。

  这几天，我一直在利用休息时间编写筛法求素数的程序，目前的程序中包含了3个版本（算法）的程序，分别位于3个文

件siftPrime1.cpp,siftPrime3.cpp,siftPrime4.cpp，见楼下的附件。3个程序的功能完全相同，都是采用分段筛的方

法，可对4G以上范围内的数进行筛选。第一个程序几乎没有用到什么技巧，采用字节数组表示每个数是素数还是和数。第

二个程序采用了很多技巧，算法同 30# 楼给出的相同，只是现在的程序结构更加优化，测试更充分，解了 n>2^32不能

正常工作的bug。第三个程序是第二个程序的改进版，采用了一个模板，这个模板预先筛去了7，11，13，17的倍数，速度

提高了大约15%。

这三个程序的性能指标（以下数据均为在 PIV 2.6G，512K L2 cache下的测试数据，仅筛并统计素数个数不输出)
             siftPrime1                siftPrime2                siftPrime3
     1亿   0.78秒                0.172秒                        0.125秒
    10亿   8.25秒                1.86秒                         1.547秒
    100亿  92.78秒                21.7秒                        18.4秒


源代码中函数接口说明:
下面是3个函数的接口,三个函数中仅名字不一样,函数接口完全一致,功能已完全一致.

UINT64 generalSift(UINT64 n,void *primeTab,int mode, UINT64 primeTabLimtCount);
UINT64 fastSift(UINT64 n,void *primeTab,int mode, UINT64 primeTabLimtCount);
UINT64 proSift(UINT64 n,void *primeTab,int mode, UINT64 primeTabLimtCount);

n表示筛的范围,如果n=1亿,将筛1-1亿之间(包括1亿)的所有素数.
primeTab 表示输出的素数表的地址,等于NULL 表示只统计个数,不输出.
mode: 表示要输出的素数表的格式,允许的取值有3个,4,8,30. 4表示输出到UINT32数组,每个素数占用4Byte,8表示输

出到 UINT64数组,每个素数占用8字节,30表示输出到素数bit表,n以内的素数暂用的空间为n/30字节,利用这个素数表可

迅速判断出n以内的任何一个数是否是素数.判断方法,将 primeTab 视为 BYTE*, 则primeTab【i】的bit0-bit7表示

i*30+(1,7,11,13,17,19,23,29)是否是和数,1:表示是合数, 0:表示是素数,值得注意的是这个表中并没有表示2,3,5这

三个素数的信息.bit数组的编码在上次那个附件的表示法和shines相反,这次改为和shines的一致.

  primeTabLimtCount 表示PrimeTab的限制长度,如mode=4,则primeTab只能容纳 primeTabLimtCount * sizeof

(DWORD)个字节,多余的将不存储.如mode=8,则primeTab只能容纳 primeTabLimtCount * sizeof(UINT64)个字节,多余

的将不存储.mode=30,则primeTab只能容纳 primeTabLimtCount个字节,多余将不存储,如果primeTabLimtCount =0,则

只统计素数个数,不存储任何素数.

  对这这个代码的输出部分进行修改,很容易改成搂住的另一个擂台所用的程序(极大素数间隔问题)

http://bbs.emath.ac.cn/thread-241-1-1.html

proSift可能是终极版本,其筛素数的速度很难有本质性的提高.

感谢shines所做的工作,他代码进行了改进,我的新版对统计素数个数时借鉴了他的一些算法.

liangbch

本帖附件包含了3个版本的源代码和测试代码，其中的三个exe文件为分别调用 generalSift，fastSift，proSift。各位网友可使用它们测试这几个版本在你自己电脑上的运行时间。
  欢迎大家下载并测试，并给出一些其他对照程序的性能数据.

tprime

很快了, 100亿在我的PD（3.2G）耗时15.984秒（VC++ 2008 express  编译最大优化）
比我现在的要快20%

无心人

刚做内存拷贝优化了 一次拷贝240240byte数据
最后优化到一次传送80字节
速度是50.094ms / 500次
2.354GB/s
不知道写个传送240字节的好不好
===========================
240字节性能反而降低