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

Crossin先生

发布于 2026-07-28 11:09:44

文章被收录于专栏：Crossin的编程教室Crossin的编程教室

大家好，欢迎来到 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 prime
print(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 prime
print(primeSum())

结果就是 1060

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

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2026-07-27，如有侵权请联系 cloudcommunity@tencent.com 删除

优化