用程序计算100以内质数之和

大家好，欢迎来到 Crossin 的编程教室。

今天给大家出道题。

题目很短：

计算1到100以内所有质数的和

所谓质数，就是除了1和此数自身外，不被其他自然数整除的数。

这是道经典的编程练习题，解法也有很多种。

一种常见的解决思路：

判断一个数是不是质数，这个不算难

找出1~100的范围内，所有的质数，这个也很简单

把找出来的质数加一起，这就更没难度啦

把上面3步合在一起就OK啦！

在往下看示例代码之前，建议大家自己动手写一写。

如果你有兴趣的话，也可以想想其他的解法，并且进一步考虑下你所用方法的算法复杂度是多少。

…

…

…

【参考解答】

常规思路是：

遍历 2~100:   判断当前数是不是质数   如果是质数，把值累加到结果上输出结果

而判断质数的基本方法是：

遍历 2~待判断数:   判断是否可以被当前数整除   如果可以整除，则不是质数如果遍历完毕都没有能整除的，则是质数

不过，这其中有不少可以优化的地方，让程序可以用更少的计算次数就可以得到结果。比如判断一个数N是否质数并不需要遍历 2~N，只需要到 √N 即可。

来自读者 @一个石头 的优化方案：

def primeSum(N=100):   initial=[]     prime=0    node=int(N**0.5)+1    for i in range(2,node):           if 0 not in [i%pr for pr in initial]:                     prime+=i                     initial.append(i)     for i in range(node,N):       if 0 not in [i%pr for pr in initial]:           prime+=i     return primeprint(primeSum())

还有一个比较有意思的解法。这个解法的思路是与常规反着的，并不是判断谁是质数，而是去掉那些不是质数的：

创建 2~100 的列表L如果列表L里还有值，则继续循环:   把L[0]的值累加到结果上   对于列表L中的元素，能被L[0]整除的通通不要，剩下的成为新的L

代码：

def primeSum(N=100):   initial = list(range(2,N+1))   prime = 0   while len(initial) > 0:       i = initial[0]       prime += i       initial = [num for num in initial if num % i != 0]   return primeprint(primeSum())

结果就是 1060

如果本文对你有帮助，欢迎点赞、评论、转发。你们的支持是我更新的动力~

购买后可加入读者交流群，Crossin为你开启陪读模式，解答你在阅读本书时的一切疑问。

Crossin的其他书籍：

感谢转发和点赞的各位~