2，因为range是包头不含尾类型，所以要+1. 172226325 发表于 2020-6-5 15:57
就是它 4-8这几段我没弄懂它的逻辑，为什么要这样分：
for i in range(2, k+2):
if m % i == 0:
为什么不这样分？
我觉得这样就好，没必要用到 math 库吧，只不过用到了效率高一丢丢
m = int(input("请输入一个整数(>1)："))
for i in range(2, m):
if m % i == 0:
print(m,'是合数！')
break
else:
print(m, "是素数！") 本帖最后由 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就可以了！ 172226325 发表于 2020-6-5 16:04
对的，感觉您的这个真的好清晰易懂，赞！。
主要是碰到了他这种解题思路，想弄明白为啥要这么分，什么 ...
嗯，这个题牵扯到数学方面的算法问题， 已经不是简单的python问题了。 本帖最后由 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, "是合数！") Twilight6 发表于 2020-6-5 15:59
我觉得这样就好，没必要用到 math 库吧，只不过用到了效率高一丢丢
不要小看算法，试试查找几位数以内的素数，你的算法和优化算法的差距随着位数上升，效率从几倍到几千几万倍成级数上升。 txxcat 发表于 2020-6-5 17:44
不要小看算法，试试查找几位数以内的素数，你的算法和优化算法的差距随着位数上升，效率从几倍到几千几万 ...
我并没有小看算法 ，单纯对本题而言 知道吧
页:
[1]