【每周一坑】​正整数分解质因数 +【解答】计算100以内质数之和

零基础python入门教程：python666.cn

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

这周我们继续和“质数”死磕。

请听题：

将一个正整数分解质因数。如果是质数，则输出“这是质数”

关于分解质因数：每个合数都可以写成几个质数相乘的形式，其中每个质数都是这个合数的因数，把一个合数用质因数相乘的形式表示出来，叫做分解质因数。分解质因数只针对合数。

例如：

输入 90，输出 2 3 3 5

输入 23，输出 这是质数

详细解答和参考代码将在下期栏目中给出，也可以参考其他同学在留言中的代码。

期待各位同学提交解答，更期待你能完成整个系列。

简单代码可直接在留言中提交，较长代码推荐使用 paste.ubuntu.com 或 

codeshare.io 等代码分享网站，只需将代码复制上去保存，即可获得一个分享地址，非常方便。

往期问题可点击文章开头的合集“每周一坑”进入查看。

---

【解答】计算100以内质数之和

本题的常规思路是：

遍历 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

---

_往期文章推荐_

【每周一坑】计算100以内质数之和

---

如需了解付费精品课程及教学答疑服务

请在Crossin的编程教室内回复: 666