2011这个素数, 最多是多少个连续素数的和?

mathematica

我把17楼的wayne的代码分解注释一下，同时他的代码稍微有些不完美的地方就是
没有给出连续的素数，只给出了连续的素数开始的位置，本人稍微补充了一下。(*2011是多少个连续素数的和*)
Clear["Global`*"];        ...
mathematica 发表于 2011-3-12 11:27

我觉得我注释的多么好呀!!!!!!!!!!赞美一下自己
几百年后我看到这段代码,依旧还是能明白代码所要表达的意思!

gw_0810

很受教

282842712474

wayne 发表于 2011-1-17 10:34
换了一种全新的思路，但代码超过了一行，不过速度又大大提高了，可以算出200万零11只有一个解：
{222161,  ...

请原谅我的挖坟呀^_^

wayne兄，你的这段代码，我在我的mathematica 9上运行，计算n=20000011（两千万零11）时，直接卡死了，我要强行重启了，你试试？

我也来一段python代码吧：

1. 
   
2. import time
   
3. start=time.clock()
   
4. import math
   
5. 
   
6. n=20000011
   
7. prime=[i for i in range(1,n+1)]#定义整数表
   
8. r=int(math.sqrt(n))
   
9. 
   
10. #下面是用删除式的方法把整数表中的合数删除掉
    
11. for j in range(2,r+1):
    
12.   if prime[j-1] != 0:
    
13.     s=j*j
    
14.     while s <= n:
    
15.       prime[s-1]=0
    
16.       s=s+j
    
17. prime.sort() #从小到大重新排列（让0位于前面）
    
18. z=prime.count(0) #统计0的个数
    
19. prime=prime[z+1:n]
    
20. #素数表生成完毕
    
21. pl=len(prime)
    
22. prime.append(n+1) #往素数表里边添加一个大数，避免溢出错误
    
23. i=1
    
24. a=0
    
25. b=0
    
26. s=2
    
27. while b<pl:
    
28.   if s<n:
    
29.     b=b+1
    
30.     s=s+prime[b]
    
31.   elif s>n:
    
32.     s=s-prime[a]
    
33.     a=a+1
    
34.   else:
    
35.     print([a+1,b+1])
    
36.     s=s-prime[a]
    
37.     a=a+1
    
38. end=time.clock()
    
39. print("time:",end-start)
    

复制代码

比较长，因为基本上没有预先加载什么，完全就是从零开始生成素数表，然后再累加比较等等。
不打算跟大家比简洁了，呵呵~但是这个代码效率还算比较高，算两千万零11时，只用了5秒（在pypy上运行）
估计该算法是\(\mathcal{O} (n)\)的

wayne

282842712474 发表于 2014-7-28 13:25
请原谅我的挖坟呀^_^

wayne兄，你的这段代码，我在我的mathematica 9上运行，计算n=20000011（两千 ...

我的没问题，耗时6秒钟，截图为证：

（Mathematica 10，windows 8.1,64bit）

282842712474

wayne 发表于 2014-7-28 23:47
我的没问题，耗时6秒钟，截图为证：

（Mathematica 10，windows 8.1,64bit）

刚刚我再运行了一次，很悲剧地，我又强行重启了一次

我的是（Mathematica 9中文版，windows 8.1,64bit），不知道wayne的mathematica有没有设置什么，比如增大了内存等等，我对mathematica不熟悉，也不好说原因。

同样的程序，计算两百万零11的时候，程序还是比较快的，显示1.15秒完成，但不知道为何两千万零11就跪了...

wayne

282842712474 发表于 2014-7-29 01:17
刚刚我再运行了一次，很悲剧地，我又强行重启了一次

我的是（Mathematica 9中文版，windows 8.1,64bit ...

我什么都没设置，是10的默认配置。

你这个是软件卡死，还是机器卡死？
如果是软件卡死的话，那很可能就是软件的bug了，或许就是版本9的bug。
如果是机器卡死的话，那估计是内存太小的缘故。 我的机器的内存是6G。
（这段代码要申请的内存空间还是不小的）

wayne

不对啊。我刚才测试了一下，凭肉眼观察，发现 n= 20 000 011 ，耗时6秒钟，内存消耗的峰值好像不到400M ，
于是我索性继续增加10倍， n= 200 000 011 ，耗时61秒钟，内存峰值接近4G。算得答案是{4893, 7996}，即第4893个素数到第7995个素数之和为200 000 011

chyanog

我也测试了一下，win8.1 32bit,2GB内存，Mathematica10运行约19s，内存占用并不夸张；然后用Mathematica9测试，果然卡死，没有强制重启一直卡了15分钟后才好转

wayne

chyanog 发表于 2014-7-29 09:21
我也测试了一下，win8.1 32bit,2GB内存，Mathematica10运行约19s，内存占用并不夸张；然后用Mathematica9测 ...

我怀疑是GatherBy函数的问题

282842712474

wayne 发表于 2014-7-29 09:34
我怀疑是GatherBy函数的问题

刚装了个10，成功运行了，果然是9的问题呀，不过用时是14.5秒，感觉wayne的机器很快呀，wayne有没有兴趣下载个pypy（pypy是绿色版的），运行一下我那个python程序，看看在你的机器上用时多少？