趣题：求500000000内的素数

jimogsh

下面的题目用mathematica来做似乎是没有一点难度的，但要在128M内存之下完成却也并不太容易，大家试试吧
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
发信人: Polaris (北极), 信区: Program
标  题: 挑战一下吧
发信站: BBS_兰大西北望 (2010-07-28 21:10:40 Wed), 站内

题目：求500000000以内的素数。
要求：
1、x86 32位平台的代码
2、内存使用不得超过128M
3、求出个数和内容即可，保存到数组里即可，只需要输出个数，不需要输出其它内容，但
是代码里必须得求出来。
4、比谁的速度更快，越快越好
5、语言不限，汇编也可以

--
那天我们交换彼此心愿，不管梦想有多遥远，
时间静止在蓝天的边缘，温热昨日风中诺言


※ 来源:·BBS_兰大西北望 bbs.lzu.edu.cn·[FROM: 61.148.56.*]

wanglu

正在用Forcal封装HugeCalc，试了一下楼主的题，也不知道对不对？
Forcal代码：

1. !using["HugeCalc"];
   
2. mvar:
   
3. t0=sys::clock();
   
4. i: a=newhc[HI].nstr["1"].free[],
   
5.    b=newhc[HI].nstr["500000000"].free[],
   
6.    i=0, a.NextPrime[a],
   
7.    while{LE(a,b),
   
8.      //printff["\r\n"], a.show[],  //执行这句，就输出结果
   
9.      a.NextPrime[a],
   
10.      i++
    
11.    },
    
12.    i;
    
13. [sys::clock()-t0]/1000;

复制代码

结果：
i: 26355867
228.922
即：500000000以内的素数为26355867个，耗时228.922秒。内存使用23468K，不到25M，我还加载了很多Forcal扩展库，这些库与本次计算没有关系。
我的机器配置：Intel Core 2 Duo T5500 1.66G 1G内存。只有一个核在使用，因为cpu使用率为50％。

wanglu

以上代码没有保存结果。
保存500000000以内的素数空间为26355867×4＝105423468B＝105M
105M＋23468K＝128M，刚好满足楼主要求，若不满足，可以不加载多余的Forcal扩展库。

发现HugeCalc中有专门的函数获取 [u32LBound, u32UBound] 内素数清单：
CONST UINT32 HugeCalc::GetPrimeList( UINT32 * CONST lpPrimeBuffer, CONST UINT32 u32LBound, CONST UINT32 u32UBound );

还没有封装该函数，估计速度会很快。

我这里是用NextPrime获得素数的，应该比较慢吧？

wanglu

很想知道mathematica用NextPrime函数（一个一个地获取）获得类似结果会有多长时间？

FreddyMusic

结果：
i: 26355867
228.922

wanglu 发表于 2010-7-30 18:41

如果仅是求，已知范围5*10^8内素数的数量的话，M8可以秒杀。

1. 
   
2. AbsoluteTiming@PrimePi[5*10^8]
   

复制代码

{0., 26355867}

计算资源不是瓶颈，这是硬件发展的趋势。高效算法还是令人欣赏的。

waynebuaa

5# FreddyMusic
仅是求个数的话，任何编程语言，任何软件都可以秒杀

FreddyMusic

way 换到题，找点有意思的题目大伙一起做做，讨论一下。

jimogsh

要把所有的素数求出来，只是不需要显示而已

waynebuaa

9# jimogsh
jimogsh，你问的问题太专业了，仅仅会玩几个Mathematica命令，而没有编程和数学深厚功底的人可以说是不可能原创性的给出很好的方法的。
================================================
看看那些真正的牛人怎么解决的吧：
http://bbs.emath.ac.cn/thread-234-1-1.html

wanglu

如果仅是求，已知范围5*10^8内素数的数量的话，M8可以秒杀。
AbsoluteTiming@PrimePi[5*10^8]
{0., 26355867}

计算资源不是瓶颈，这是硬件发展的趋势。高效算法还是令人欣赏的。
FreddyMusic 发表于 2010-7-31 09:10

很想知道mathematica用NextPrime函数（一个一个地获取）获得类似结果会有多长时间？

例如：从1开始，NextPrime[1]为2，计数增1，然后NextPrime[2]为3，计数再增1，然后NextPrime[3]为5，计数再增1，... ...，直到5*10^8，计数值应是26355867，看一下时间是多少？

这个随没有多大意思，但我还是很想知道这个结果（有比较才能有进步），能否帮一下忙？或者其他朋友也可帮忙测一下？

waynebuaa

10# wanglu
楼上的是不是想对照一下 各大数学软件使用同一算法的性能啊

呵呵，俺觉得这种想法是很好的，但对很多高级软件来说，是非常不公平的，因为任何高端语言里面使用For之类的循环，效率肯定都是极其低的。

要比，就应该跟C，C++里面对应的数学库比，比如GMP，CLN，NTL等等

waynebuaa

:victory:

俺非常看好forcal，加油！！

wanglu

10# wanglu
楼上的是不是想对照一下 各大数学软件使用同一算法的性能啊

呵呵，俺觉得这种想法是很好的，但对很多高级软件来说，是非常不公平的，因为任何高端语言里面使用For之类的循环，效率肯定都是极其低的 ...
waynebuaa 发表于 2010-8-3 09:25

首先谢谢waynebuaa 的鼓励！

如果循环中调用了耗时相对较长的函数，脚本的效率就不会非常低的，如本例的NextPrime耗时相对较长，恐怕在228.922秒中占了大部分时间吧？这个我没有测试。

mathematica的NextPrime函数也是非常优秀的，而mathematica也是通过脚本调用NextPrime函数的，故想用Forcal＋HugeCalc与之比较一下，找找差距，呵呵。

waynebuaa

能在HugeCalc这个级别比较的，估计也就gmp了，楼主不妨试试  Forcal+GMP  ？
http://gmplib.org/

wanglu

能在HugeCalc这个级别比较的，估计也就gmp了，楼主不妨试试  Forcal+GMP  ？
http://gmplib.org/
waynebuaa 发表于 2010-8-4 09:28

看过HugeCalc和gmp比较的帖子，能实现Forcal+GMP  也是很不错的。可惜俺英语很菜，在封装IMSL时就因很吃力而暂停了。
HugeCalc在很多方面超过了gmp，有作者的支持，封装会很方便，也是对国货精品的支持。因HugeCalc和gmp有类似的功能，以后即便要实现Forcal+GMP  也很方便的。