求10的10次方以内的素数，怎么能在几小时内算出来结果？

arust

原帖由 win_hate 于 2009-4-25 13:44 发表


我也是这样想的。求素数个数本质上是另一个问题。

我测试了一下，似乎不是这样的
计算1 ~ 900000000 之间的质数，并把结果写入文件当中，只耗时0.035853s，生成的文件有400多M，生成文件耗时28193.508ms。内存和硬盘比较大的朋友可以尝试选择更大的范围

arust

又计算了1~999999999之间的质数，这是生成的文件，依然很快，不超过0.1秒

[ 本帖最后由 arust 于 2009-4-30 13:37 编辑 ]

redspider

原帖由 arust 于 2009-4-30 13:28 发表


我测试了一下，似乎不是这样的
计算1 ~ 900000000 之间的质数，并把结果写入文件当中，只耗时0.035853s，生成的文件有400多M，生成文件耗时28193.508ms。内存和硬盘比较大的朋友可以尝试选择更大的范围

哇塞，你怎么算的？

win_hate

原帖由 arust 于 2009-4-30 13:28 发表


我测试了一下，似乎不是这样的
计算1 ~ 900000000 之间的质数，并把结果写入文件当中，只耗时0.035853s，生成的文件有400多M，生成文件耗时28193.508ms。内存和硬盘比较大的朋友可以尝试选择更大的范围

我看了一下 HugeCalc  的说明：

http://www.emath.ac.cn/hugecalc/index.htm#PrimeNumber

里面有一段:
......
未卜先知：任意设定一个范围，可以在零点几秒内快速计算出该范围内的素数个数，并告诉用户，如果输出，将会有多少行、多少字节，这可都是在数微秒内精确计算出来的！比如说，如果需要保存 [0，4294967295] 内的全部素数，将需要 2,206,763,134 字节，我可不希望用户来抱怨“按个回车键后就得去欣赏硬盘的嘎吱嘎吱声”，所以特别提供了上下限范围可编辑的功能，结束后，再按“<--”或 “-->”即可继续搜寻等幅大小邻域内的素数；
......

我猜 HugeCalc 是在输出时才计算具体素数的。

win_hate

某范围内的素数个数，第 n 个素数值都是有有效算法的。

0～10^10 间的素数个数：

PrimePi[10^10]
455052511

第 50000000000 个素数
Prime[50000000000]  
1344326694119

计算 10^10 内素数个数的耗时

Timing[PrimePi[10^10]]
{0.184011, 455052511}

redspider

HugeCalc 只有 DLL 形式的库，只能在 win 上用

arust

原帖由 win_hate 于 2009-4-30 14:43 发表


我看了一下 HugeCalc  的说明：

http://www.emath.ac.cn/hugecalc/index.htm#PrimeNumber

里面有一段:
......
未卜先知：任意设定一个范围，可以在零点几秒内快速计算出该范围内的素数个数，并告诉 ...

即便如此，HugeCalc 的速度依然惊人。我刚才又测试了一下，计算的质数范围从 2 ~ 1, 999, 999, 999（内存小，只能计算这么大范围了），因为 HugeCalc 在计算范围比较大的时候，时间计算不准确，我只能从cpu占用情况来估算计算时所花的时间，刚开始，cpu占用率维持在50%左右，大概持续了2秒左右，这个应该是真实的计算时间。然后cpu占用率就下降到10%左右，这应该是往磁盘上写入数据。最后生成的文件大小接近1G。

hhhhkkkk

用java写了一个，大约要2个小时，看来java做这个不行啊。