【每周一坑】正整数分解质因数 +【解答】计算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 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

_往期文章推荐_

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

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

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

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

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