求十亿内所有质数的和，怎么做最快? 第1页

这个题目下的答案大致分为几种：

1. Magic。例如 @陈硕， @渡子厄（半Magic，因为Wolfram Alpha并没给出准确结果）。这个我就不评论了，因为没说是什么方法。
2. 暴力1到10亿，对每个数判断是否素数（或暴力试除，或Miller Rabin）。方法太暴力，最快也不过，其中是上界10亿。
3. 筛出所有以内的素数然后加起来。有人用Eratosthenes筛（复杂度），有人用欧拉筛（最简单的线性筛之一），也有人用Matlab等软件。此方法也极其暴力。因为不超过n的素数有个，所以任何先找出所有素数再加起来的方法（即使使用亚线性的筛法，例如Atkin筛或Wheel筛）都不可能快于这个时间复杂度。
4. 不知所云型。就不点名了。
5. 理论上更优的算法。目前只看到 @罗宸。他给出的代码是来自于Project Euler第10题（Summation of primes ）的论坛中Lucy_Hedgehog给出的Python代码的直接翻译，注释也都还在。接下来我就来介绍一下Lucy_Hedgehog给出的这个算法。

==========正式回答分割线=============

首先来感受一下这个算法的速度：

       $ for n in 10000000 100000000 1000000000 10000000000 100000000000; do time python Main.py $n; done 3203324994356  real    0m0.049s user    0m0.031s sys     0m0.015s 279209790387276  real    0m0.117s user    0m0.093s sys     0m0.015s 24739512092254535  real    0m0.514s user    0m0.468s sys     0m0.046s 2220822432581729238  real    0m2.645s user    0m2.625s sys     0m0.031s 201467077743744681014  real    0m15.713s user    0m15.656s sys     0m0.031s      

可以看到，即使是python这样的解释型动态语言，算出10亿的结果也不过需要0.5s，算出1000亿也只要15秒，是完虐以上各种暴力方法的。

整个算法类似于Wikipedia中给出的求n以内素数个数的算法（

），感兴趣的也可以去看一下。

==========真正的！正式回答分割线 :D =============

定义为到所有整数中，在普通筛法中外层循环筛完时仍然幸存的数的和。因此这些数要不本身是素数，要不其最小的素因子也大于。因此我们需要求的是，其中是十亿。

为了计算，先考虑几个特殊情况

1. 。此时所有数都还没有被筛掉，所以
   
2. 不是素数。因为筛法中早已被别的数筛掉，所以在这步什么都不会做，所以此时；
3. 是素数，但是。因为每个合数都一定有一个不超过其平方根的素因子，如果筛到时还没筛掉一个数，那么筛到时这个数也还在。所以此时也有。

现在考虑最后一种稍微麻烦些的情况：是素数，且。

此时，我们要用素数去筛掉剩下的那些数中的倍数。注意到现在还剩下的合数都没有小于的素因子。因此有：

后面那项中提取公共因子，有：

因为整除，稍微变形一下，令，有：

注意到一开始提到的的定义（“这些数要不本身是素数，要不其最小的素因子也大于(注意!)”），此时后面这项可以用来表达：

再用替换素数和得到最终表达式：

我们最终的结果是。计算时可以使用记忆化，也可以直接自底向上动态规划。

至于算法的复杂度就留作练习，是低于以上任何一种暴力方法的。

希望我讲清楚了。代码我就不放了，自己解决Project Euler 第10题之后可以去论坛里看Lucy_Hedgehog的代码（在论坛第5页）。也可以去看

给出的代码。

========== 更新：

在评论中给出一个链接，其中包含一个理论上更优的算法（

上

）。我粗略读了一下，认为理论上是可行的。因为本题中的答案只有级别，使用中国剩余定理的话也只需要算到级别的素数，因此总复杂度为。

粗略读了下其参考文献（J. C. Lagarias and A. M. Odlyzko,

,

8 (1987), pp. 173-191. ）后，我认为这算法不可能像这个答案中的算法一样在十几行代码内实现，仅放出来供感兴趣的朋友去看一下。