level 2
我用mathematica计算使用如下代码:
Total[Prime[Range[PrimePi[10^9]]]]
等了很久都没有出来结果,是因为mma求质数效率比较低吗?或者有没有更好的代码可以求得更快?
2018年05月15日 05点05分
1
吧务
level 11
不是求素数的函数执行效率低,是这段代码算法的问题。
首先,内存消耗很大,因为涉及1到50847534的序列,还涉及相同数量的素数,内存消耗很大,估计在运行的时候你的电脑应该是无响应的状态,你说的等了很长时间都没结果应该是内存消耗大,电脑已经无响应了。
其次,涉及50847534次求素数,还涉及50847534次加法,所以需要花费很长时间是必然的。
一个稍微改进的算法,采用尾递归,至少内存问题可以解决。时间问题,可能还需要更好的算法。
sumPrime[sum_, _, 0] := sum
sumPrime[sum_, next_, n_] := sumPrime[sum + next, NextPrime[next], n - 1]
sumPrime[0, 2, PrimePi[10^9]] // AbsoluteTiming
{1937.19, 24739512092254535}
2018年05月16日 02点05分
2
吧务
level 9
你如果仔细看知乎上的那个链接,其实已经有了比较好的代码了,另外还有个类似的链接mathematica.stackexchange.com/questions/80291/efficient-way-to-sum-all-the-primes-below-n-million-in-mathematica/80406
以前还将Matlab的primes函数(生成N以内的所有素数)翻译成Mathematica版,用在这里虽然不是很高效,但还说得过去,1亿内的不到2秒,十亿内的不到1分钟
primes[n_] := Module[{p = Range[1, n, 2]},
p[[1]] = 2;
Do[If[p[[(k + 1)/2]] != 0, p[[(k^2 + 1)/2 ;; ;; k]] = 0],
{k, 3, n^.5, 2}];
SparseArray[p]["NonzeroValues"]
];
primes[10^8] // Total // AbsoluteTiming
primes[10^9] // Total // AbsoluteTiming
2018年05月16日 03点05分
3