鱼C论坛

 找回密码
 立即注册
查看: 1088|回复: 12

求问大神

[复制链接]
头像被屏蔽
发表于 2020-6-5 15:47:16 | 显示全部楼层 |阅读模式
提示: 作者被禁止或删除 内容自动屏蔽
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2020-6-5 15:50:46 | 显示全部楼层
1,因为是从2开始的,要补上
2,因为range是包头不含尾类型,所以要+1.
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

头像被屏蔽
 楼主| 发表于 2020-6-5 15:57:27 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-6-5 15:58:45 | 显示全部楼层
172226325 发表于 2020-6-5 15:57
就是它 4-8这几段我没弄懂它的逻辑,为什么要这样分:
for i in range(2, k+2):
  if m % i == 0:

为什么不这样分?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-6-5 15:59:53 | 显示全部楼层


我觉得这样就好,没必要用到 math 库吧,只不过用到了效率高一丢丢
m = int(input("请输入一个整数(>1):"))
for i in range(2, m):
    if m % i == 0:
        print(m,'是合数!')
        break 
else:
    print(m, "是素数!")
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

头像被屏蔽
 楼主| 发表于 2020-6-5 16:04:57 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-6-5 16:08:49 | 显示全部楼层
本帖最后由 Twilight6 于 2020-6-5 16:20 编辑
172226325 发表于 2020-6-5 16:04
对的,感觉您的这个真的好清晰易懂,赞!。

主要是碰到了他这种解题思路,想弄明白为啥要这么分,什么 ...


我可能想到为啥了  因为range(2, k +2)  最后 i 值可以取到 k +1 然后对 if 如果 i == k +1 说明全部循环除了一次
就可以进行判断了是不是素数了~

刚刚去百度的结果,参考下:
这属于算法上的问题,好好考虑一下算法,还要考虑一下素数的定义。
素数是只有1和本身能整除的整数。所以在求素数的时候,要将素数与1到素数本身中间的所有整数都相除,看是否有整除的数,如果有,那肯定不是素数了。但是从算法上考虑,为了减少重复量,开平方后面的数就不用相除了,因为a/b(平方数)=c(小一点的数),同样a/c=b。举例说明:
25,开平方以后是5,那么整除2~5就可以了,如果有满足条件的,就是素数。
这样做可以减少循环次数,素数是因子为1和本身, 如果数c不是素数,则还有其他因子,其中的因子,假如为a,b.其中必有一个大于sqrt(c) ,一个小于sqrt(c) 。所以m必有一个小于或等于其平方根的因数,那么验证素数时就只需要验证到其平方根就可以了。即一个合数一定含有小于它平方根的质因子。

再比如:24的因数有1、2、3、4、6、8、12、24
按定义应该用2-23去除,但经过分析上面的数可以发现
1×24、2×12、3×8、4×6
如果2、3、4是某个数的因数,那么另外几个数也是,反之也一样
所以为提高效率,可以只检查小于该数平方根的那些数,如24的平方根大于4小于5,检查2-4就可以了!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-6-5 16:14:27 | 显示全部楼层
172226325 发表于 2020-6-5 16:04
对的,感觉您的这个真的好清晰易懂,赞!。

主要是碰到了他这种解题思路,想弄明白为啥要这么分,什么 ...

嗯,这个题牵扯到数学方面的算法问题, 已经不是简单的python问题了。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

头像被屏蔽
 楼主| 发表于 2020-6-5 16:20:29 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

头像被屏蔽
 楼主| 发表于 2020-6-5 16:21:19 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-6-5 17:40:23 | 显示全部楼层
本帖最后由 txxcat 于 2020-6-5 17:46 编辑

你的代码其实是有问题的,倒不是说不能正确运行,只是一点点的效率问题,多循环了一次而已,但正好涉及到你要问的两个问题,所以只有修正后再去分析才能弄明白逻辑:
import math
m = int(input("请输入一个整数(>1):"))
k = int(math.sqrt(m))
for i in range(2, k+1):       #<---正确的算法是算到平方根取整+1,多一个都不用算了,原因7楼Twilight6百度的已经说得很清楚了
    if m % i == 0:
        break #可以整除,肯定不是素数,结束循环
if i == k:                            #<---相应这里k要去掉+1,因为上面已经改成正确的循环次数了,这个是判断循环是否完整运行,如果i的值等于k,说明循环已经运行完了最后一步,也就是没有发现可以整除的数,那么就是素数,还有一种判断方法是用一个变量来判断,后面代码演示
    print(m, "是素数!")
else:
    print(m, "是合数!")
如果你理解了那两个问题,这段代码还有一个问题就是内置函数可以求平方根,没必要用math模块这么麻烦了,然后顺便演示一下另外一种判断写法:
m = int(input("请输入一个整数(>1):"))
k = int(m**0.5)       #<----求平方根就这么简单,何须求助math
prime=True    #<---加入一个变量,默认值为True,当然设为1也行
for i in range(2, k+1):
    if m % i == 0:
        prime=False    #<---可以整除,prime设为False,不是素数
        break
if prime:
   print(m, "是素数!")
else:
   print(m, "是合数!")
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-6-5 17:44:13 | 显示全部楼层
Twilight6 发表于 2020-6-5 15:59
我觉得这样就好,没必要用到 math 库吧,只不过用到了效率高一丢丢

不要小看算法,试试查找几位数以内的素数,你的算法和优化算法的差距随着位数上升,效率从几倍到几千几万倍成级数上升。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-6-5 17:47:11 | 显示全部楼层
txxcat 发表于 2020-6-5 17:44
不要小看算法,试试查找几位数以内的素数,你的算法和优化算法的差距随着位数上升,效率从几倍到几千几万 ...

我并没有小看算法 ,单纯对本题而言 知道吧
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-1-20 22:46

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表