ReaderMX.
Crossin的编程教室

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

CCrossin先生约 3 分钟

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

今天给大家出道题。

题目很短：

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

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

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

一种常见的解决思路：

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

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

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

把上面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编著《码上行动：用ChatGPT学会Python编程》现已上市。本书以AI为辅助，系统全面地讲解了如何掌握Python编程，适合Python零基础入门的读者学习。【点此查看详细介绍】
购买后可加入读者交流群，Crossin为你开启陪读模式，解答你在阅读本书时的一切疑问。
Crossin的其他书籍：
添加微信 crossin123 ，加入编程教室共同学习~
Image
感谢转发和点赞的各位~

KEEP THE THREAD GOING

更多来源文章