论坛 › 编程擂台 › 10秒内计算出1亿素数表, 不输出

qianyb 发表于 2010-4-2 10:25:07

我只要求输出到文件而已，用不着这么多的内存
如果不输出的话，计算100亿需要多少内存呢？

gxqcn 发表于 2010-4-2 10:40:32

输出到文件，内存耗用最大的阶段是准备字符串输出。
如果不输出的话，仅计数内存耗用是很小的；
即便是标记素数，也可以每8个bits标记区间长度为30的素数分布情况。
（因为除了前30个自然数外，每30个连续正整数数中素数最多不超过8个，按其模30剩余分类即可）

qianyb 发表于 2010-4-2 11:28:35

输出到文件，内存耗用最大的阶段是准备字符串输出。

这个应该不大啊，你不会一个文件一起写进去吧，可以分块写啊

gxqcn 发表于 2010-4-2 13:07:27

我不想把程序搞的太复杂。
既然已经提供任意区间内素数的搜索与输出，所以就不再设计分块写的功能了。
况且一般用户也不需要很大的素数库。

liangbch 发表于 2010-4-2 16:51:39

对于一个程序的功能和特性来说，在许多时候，不是做不到，而是值得不值得花时间去实现。没有100%完美的的程序，对程序的改进是无止尽的。作为一个开发者，他的精力和时间是有限的，他需要平衡程序的功能和工作量，他必须学会放弃。
我也常常使用这个程序分解素数，但是这个程序不能分解32bit以上的数，许多时候不得不自己用windows计算器去做，我理解作者的设计，如果将数的范围增加到64bit，给带来很多麻烦。

tprime 发表于 2010-12-23 14:44:02

这个程序和郭老大的素数PrimeNumber界面类似, 是ecprime的作者的改进版,支持64位整数计算和多核心优化,代码编译可不用UI.

我下载编译的运行过程
D:\Prime\primesieve\out>primesieve.exe 0 e10
Sieve size set to 64 KiloBytes
100%
Prime numbers: 455052511
Time elapsed: 3.696 sec

D:\Prime\primesieve\out>primesieve.exe e16 e9
Sieve size set to 64 KiloBytes
100%
Prime numbers: 27153205
Time elapsed: 2.854 sec

D:\Prime\primesieve\out>
http://code.google.com/p/primesieve/

mizne 发表于 2011-3-20 02:30:10

相当强大的

liangbch 发表于 2011-6-2 01:12:51

肯定要确实筛出来啦。统计个数，挑战1秒100亿差不多。
风云剑 发表于 2008-3-13 12:38 http://bbs.emath.ac.cn/images/common/back.gif

从 http://www.hackchina.com/cont/187096 看到一个计算PI(n)的代码，试用了一下，计算40亿以内素数的个数，仅需0.125秒。
下面是源代码，不知道性能比GXQ的如何。

gxqcn 发表于 2011-6-2 08:00:56

看了下源码，核心算法是一样的，性能应该不会有突破。

liangbch 发表于 2011-6-2 12:05:19

99# gxqcn

有时间研究下这个算法。

查看完整版本: 10秒内计算出1亿素数表, 不输出