求素数有一段看不懂
已经用另一段代码实现了求素数效果，但标准答案其中一段看不懂
def IsPrime(n):
if n <= 1 or n % 2 == 0 and n != 2:
return False
elif n == 2:
return True
else:
for i in range(3,n,2):
if n % i == 0:
return False
if i * i > n:
break
return True
for i in range(100):
if( IsPrime(i)):
print(i,end = " ")
if i * i > n:
break
这段看不懂什么含义 求素数时，为了减少循环次数，不都是用这玩意吗，如果检索到平方根还是没有发现因子，就不用继续扫描了，原因可以自己思考 本帖最后由 jackz007 于 2022-10-22 18:13 编辑
这个代码可否看懂？
def IsPrime(n):
r = False
if n > 1:
for i in range(2 , n):
if n % i == 0 : break
else:
r = True
return r
for i in range(100):
if( IsPrime(i)):
print(i,end = " ")
至于为什么
if i * i > n:
break
看看下面的代码：
n = 256
for i in range(2 , n):
if n % i == 0:
print("%3d = %3d x %3d" % ( n , n // i , i))
这个代码是用来寻找 256 所有因子的，再来看看运行结果
D:\\Python>python x.py
256 = 128 x 2
256 =64 x 4
256 =32 x 8
256 =16 x16
256 = 8 x32
256 = 4 x64
256 = 2 x 128
明眼人一看就能明白，循环过程多用了近一倍，以 256 = 16 x 16 为界，后半部分其实就是重复了前半部分的结果而已，完全没有必要。所以，对于寻找 256 的因子而言，只需要在 2 ~ 16 ，也就是 2 ~ sqrt(256) 的范围内寻找即可，这样可以避免多余的计算和判断，有效提高代码效率。
那么，现在再来看看这条语句
if i * i > n:
break
其中的道理就不用多作解释了吧？ 本帖最后由 jcpython2 于 2022-10-22 23:36 编辑
jackz007 发表于 2022-10-22 17:00
这个代码可否看懂？
至于为什么
抱歉老哥，奋斗五个小时了，我还没解出来
我只能回答你你那段代码我应该是理解的
def IsPrime(n):
r = False
if n > 1:
for i in range(2 , n):
if n % i == 0 : break
else:
r = True
return r
for i in range(100):
if( IsPrime(i)):
print(i,end = " ")
""""""""""
这段代码看明白
函数内假设代入7
分别循环 % 2 3 4 5 6
余 2 得1
余 3 得1
余 4 得3
余 5 得2
余 6 得1
7内所有数均没有触发==0break跳出循环
for循环自动进入else部分
r 赋值为True
这里主要通过质数的一个判定条件:质数成立的条件是1和自身外没有其他因子(除不尽,必然有余数)
1和这个数自身先不考量,也就是某数除去 2到这个数-1 范围内 都除不尽
他必然只能除1和自己能除尽
所以他是质数
PS:这里学到了for完没停止循环就自动进入else用法
"""""""""
至于我那个 i * i > n 问题，我试着搜索质数 因子 余数等数学概念并结合你说的内容，都找不到我能理解到的内容。
我整晚在一步一步一个数一个数代入代码中，最后别说逻辑了，脑子转不过来了，我明早早起再试试
现在我能勾勒到的就是
减低循环检索次数，增加程序效率,但个中原理无法吃透，可能是数学逻辑我没基础的缘故
以下是我无用功的备注，现在写完脑子乱了，转不过来
def IsPrime(n):
if n <= 1 or n % 2 == 0 and n != 2:
#n触发0和1或 n无余数能除尽并且不为2（012为质数）
return False
elif n == 2:
return True
else:
for i in range(3,n,2):
#假设n = 13进入for循环,i为 3_5_7_9_11
#假设轮到 i = 3
if n % i == 0: #13 % 3 == 3不触发
return False
if i * i > n: #3 * 3 > 13不触发 3不触发到跳出，循环继续到5
break
return True
for i in range(20): #假设 i 轮到13代入函数
if( IsPrime(i)):
print(i,end = " ")
本帖最后由 jackz007 于 2022-10-22 23:47 编辑
jcpython2 发表于 2022-10-22 23:24
抱歉老哥，奋斗五个小时了，我还没解出来
我只能回答你你那段代码我应该是理解的
3 楼用实例说明的为什么寻找目标数 n 因子时的枚举范围应该是 2 ~ sqrt(n) ，自以为讲解得非常简单、清楚、明白，没想到还是让你没看懂，我想问一下，你到底仔细看了没有？真的就没有明白点什么？再次提示你一下，以 256 = 16 x 16 为轴，上下两边对称位置上的等式是完全一样的。这一点，居然没有让你看出来？
既然一样，那就只需要循环一半次数就够了呀，这个还不顺理成章？？？ 本帖最后由 jcpython2 于 2022-10-23 00:50 编辑
jackz007 发表于 2022-10-22 23:38
3 楼用实例说明的为什么寻找目标数 n 因子时的枚举范围应该是 2 ~ sqrt(n) ，自以为讲解得非常 ...
老哥我对你给出的提示代码是有认真阅读，并且每字每句都看的，我还百度了各个提到的数学概念
如我上面的图片
https://xxx.ilovefishc.com/forum/202210/22/233624e4gccqmzzcdolpug.jpg.thumb.jpg
我知道你想引导告诉我范围应该循环一半即可
就像 x = a *b检查过后无需再检查x = b * a
我也是遵循这个方向去思考
我代码中的备注
#假设n = 13进入for循环,i为 3_5_7_9_11
#假设轮到 i = 3
#3 * 3 > 13不触发 3不触发到跳出，循环继续到5
然后i 到5后
i * i > 13 触发return True
确定13为质数？？？？ 后面7_9_11不需要再检查
那么……那么
我在写这个回复的时候写到这里我自己纳闷，我想到哪里去？我怎么好像脑子跟手脱钩了？
{:10_291:}
=============
缓了一下
当判断13的时候先是判断3，没有跳出循环没返回True，然后到i = 5
if n % i == 0: #13 % 5 == 3不触发
return False
然后
5 * 5 > 13
触发
return True
所以当判断13是否素数的时候，理论需要让13 % 2~12
但判断到5的时候就正式确定13就是素数
所以为什么5到就是素数呢
你给的提示，跟这个沾边但我又无法理解到这个点
数学基础差，确实吃不过来，先睡一觉，明日再挣扎 1 本帖最后由 Stubborn 于 2022-10-24 17:59 编辑
什么叫素数，除开1和本身，不能被其他数整除。
针对你的代码而言，下面这一行代码往上处理了什么数字，1，2，和偶数，被剔除。偶数剔除后，筛选的步长则设置为2
for i in range(3,n,2):
下面这行代码而言，对一个整数而言，i*i > n 后面可以不用搜锁，你不理解为什么，100可以被整除的数字包括这些。
如果一个整数N可以被整除，你只需要搜索 1 ~ i * i >N ，如果i~N还存在可以被整除的数字，那么结果肯定是比I小。但是1~I的区间，程序已经搜索过。没有必要搜索。
所以综合而言，程序只需要搜索1 ~ i * i >N 范围的数字，这个区间的数字都不能被整除，那么这个数字肯定是一个素数
if i * i > n: Stubborn 发表于 2022-10-24 17:48
什么叫素数，除开1和本身，不能被其他数整除。
针对你的代码而言，下面这一行代码往上处理了什么数字，1， ...
经过各位老哥的热心解释，我已经基本勾勒出你们指导的原理
但你能用运算过程做一次我看看么
打比方 100 整除的是1, 2, 4, 5, 10, 20, 25, 50, 100
那么i * i >N 其实就判断到10 * 10 > 100，后面20 25 50 100也不判断了
也如3楼老哥说的，你们举例都是某数里面的因子来说这个，比如100里面因子或者256里面因子
那么现在我这个是 %不是*
能用%的方式说一遍吗，谢谢 jcpython2 发表于 2022-10-27 16:11
经过各位老哥的热心解释，我已经基本勾勒出你们指导的原理
但你能用运算过程做一次我看看么
不明白你的问题 Stubborn 发表于 2022-10-24 17:48
什么叫素数，除开1和本身，不能被其他数整除。
针对你的代码而言，下面这一行代码往上处理了什么数字，1， ...
我所理解的你这段话是:判断100内是否能被整除只需要判断到10
因为100 除以1~10得出的数肯定少于100除以20~100的数,就因为后面的数除的值更少就不需要判断?为什么?
说回我的代码.
我的那行代码i * i是在判断素数途中,那么上面那个除一半就够,和这行代码有什么具体关系??
老哥我基础是真的比较差，你可以不需要继续回答的，我感觉也是有点勉强 jcpython2 发表于 2022-10-28 16:29
我所理解的你这段话是:判断100内是否能被整除只需要判断到10
因为100 除以1~10得出的数肯定少于100除 ...
因为100 除以1~10得出的数肯定少于100除以20~100的数,就因为后面的数除的值更少就不需要判断?为什么?
回答：任意一个数字N，你看成 I * J = N（I>=J）
当J大于I的时候，出现什么情况？比如I=20，J=5，但是你在搜索的时候I=5这个结果就已经搜索过了。你不要觉得I=5,和I=20不一样，在这个过程这种，它们都代表一个情况，可以被整除。所以才说，超过一个临界值，就不需要再判断了。
上面那个除一半就够,和这行代码有什么具体关系??
是指步长吗？步长就是剔除偶数不计算在内
页:
[1]