数学研发论坛

 找回密码
 欢迎注册
楼主: 无心人

[讨论] 10秒内计算出1亿素数表, 不输出

[复制链接]
发表于 2010-4-2 10:25:07 | 显示全部楼层
我只要求输出到文件而已,用不着这么多的内存
如果不输出的话,计算100亿需要多少内存呢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-4-2 10:40:32 | 显示全部楼层
输出到文件,内存耗用最大的阶段是准备字符串输出。
如果不输出的话,仅计数内存耗用是很小的;
即便是标记素数,也可以每8个bits标记区间长度为30的素数分布情况。
(因为除了前30个自然数外,每30个连续正整数数中素数最多不超过8个,按其模30剩余分类即可)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-4-2 11:28:35 | 显示全部楼层
输出到文件,内存耗用最大的阶段是准备字符串输出。

这个应该不大啊,你不会一个文件一起写进去吧,可以分块写啊
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-4-2 13:07:27 | 显示全部楼层
我不想把程序搞的太复杂。
既然已经提供任意区间内素数的搜索与输出,所以就不再设计分块写的功能了。
况且一般用户也不需要很大的素数库。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-4-2 16:51:39 | 显示全部楼层
对于一个程序的功能和特性来说,在许多时候,不是做不到,而是值得不值得花时间去实现。没有100%完美的的程序,对程序的改进是无止尽的。作为一个开发者,他的精力和时间是有限的,他需要平衡程序的功能和工作量,他必须学会放弃。
  我也常常使用这个程序分解素数,但是这个程序不能分解32bit以上的数,许多时候不得不自己用windows计算器去做,我理解作者的设计,如果将数的范围增加到64bit,给带来很多麻烦。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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/

评分

参与人数 1贡献 +3 收起 理由
gxqcn + 3 链接有参考价值

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-3-20 02:30:10 | 显示全部楼层
相当强大的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-6-2 01:12:51 | 显示全部楼层
肯定要确实筛出来啦。统计个数,挑战1秒100亿差不多。
风云剑 发表于 2008-3-13 12:38


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

primeNumber.rar

1019 Bytes, 下载次数: 13, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-6-2 08:00:56 | 显示全部楼层
看了下源码,核心算法是一样的,性能应该不会有突破。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-6-2 12:05:19 | 显示全部楼层
99# gxqcn

有时间研究下这个算法。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2020-12-5 20:18 , Processed in 0.061322 second(s), 18 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表