当前位置:网站首页>【每周一坑】正整数分解质因数 +【解答】计算100以内质数之和
【每周一坑】正整数分解质因数 +【解答】计算100以内质数之和
2022-07-06 12:23:00 【Crossin的编程教室】
零基础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
_往期文章推荐_
如需了解付费精品课程及教学答疑服务
请在Crossin的编程教室内回复: 666
边栏推荐
- BUUCTF---Reverse---easyre
- 8086 instruction code summary (table)
- 22-07-05 upload of qiniu cloud storage pictures and user avatars
- Color is converted to tristimulus value (r/g/b) (dry stock)
- Wechat applet common collection
- AsyncHandler
- Cesium Click to draw a circle (dynamically draw a circle)
- Tencent Android development interview, basic knowledge of Android Development
- 数字三角形模型 AcWing 1018. 最低通行费
- 解剖生理学复习题·VIII血液系统
猜你喜欢
Speech recognition (ASR) paper selection: talcs: an open source Mandarin English code switching corps and a speech
Leetcode question 283 Move zero
Tencent byte and other big companies interview real questions summary, Netease architects in-depth explanation of Android Development
22-07-05 七牛云存储图片、用户头像上传
Tencent T3 teaches you hand in hand. It's really delicious
Web security - payload
02 basic introduction - data package expansion
腾讯架构师首发,2022Android面试笔试总结
How does kubernetes support stateful applications through statefulset? (07)
数字三角形模型 AcWing 1018. 最低通行费
随机推荐
2022年6月语音合成(TTS)和语音识别(ASR)论文月报
【每周一坑】输出三角形
Period compression filter
How to handle the timeout of golang
JMeter server resource indicator monitoring (CPU, memory, etc.)
logstash高速入口
02 basic introduction - data package expansion
An East SMS login resurrection installation and deployment tutorial
js获取浏览器系统语言
解剖生理学复习题·VIII血液系统
Digital triangle model acwing 1018 Minimum toll
POJ 3207 Ikki' s Story IV – Panda' s Trick (2-SAT)
beegfs高可用模式探讨
腾讯架构师首发,2022Android面试笔试总结
Wonderful coding [hexadecimal conversion]
腾讯T4架构师,android面试基础
案例 ①|主机安全建设:3个层级,11大能力的最佳实践
【云原生与5G】微服务加持5G核心网
句号压缩过滤器
mod_ WSGI + pymssql path SQL server seat