[已解决]求素数有一段看不懂

jcpython2

已经用另一段代码实现了求素数效果，但标准答案其中一段看不懂

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 17:00:20

        这个代码可否看懂？

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:\[00.Exerciese.2022]\Python>python x.py
256 = 128 x   2
256 =  64 x   4
256 =  32 x   8
256 =  16 x  16
256 =   8 x  32
256 =   4 x  64
256 =   2 x 128

         明眼人一看就能明白，循环过程多用了近一倍，以 256 = 16 x 16 为界，后半部分其实就是重复了前半部分的结果而已，完全没有必要。所以，对于寻找 256 的因子而言，只需要在 2 ~ 16 ，也就是 2 ~ sqrt(256) 的范围内寻找即可，这样可以避免多余的计算和判断，有效提高代码效率。
        那么，现在再来看看这条语句

    if i * i > n  : 
        break

        其中的道理就不用多作解释了吧？

跳转到最佳答案楼层

wp231957

求素数时，为了减少循环次数，不都是用这玩意吗，如果检索到平方根还是没有发现因子，就不用继续扫描了，原因可以自己思考

jackz007

        这个代码可否看懂？

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:\[00.Exerciese.2022]\Python>python x.py
256 = 128 x   2
256 =  64 x   4
256 =  32 x   8
256 =  16 x  16
256 =   8 x  32
256 =   4 x  64
256 =   2 x 128

         明眼人一看就能明白，循环过程多用了近一倍，以 256 = 16 x 16 为界，后半部分其实就是重复了前半部分的结果而已，完全没有必要。所以，对于寻找 256 的因子而言，只需要在 2 ~ 16 ，也就是 2 ~ sqrt(256) 的范围内寻找即可，这样可以避免多余的计算和判断，有效提高代码效率。
        那么，现在再来看看这条语句

    if i * i > n  : 
        break

        其中的道理就不用多作解释了吧？

jcpython2

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

jcpython2 发表于 2022-10-22 23:24
抱歉老哥，奋斗五个小时了，我还没解出来

我只能回答你你那段代码我应该是理解的

       3 楼用实例说明的为什么寻找目标数 n 因子时的枚举范围应该是 2 ~ sqrt(n) ，自以为讲解得非常简单、清楚、明白，没想到还是让你没看懂，我想问一下，你到底仔细看了没有？真的就没有明白点什么？再次提示你一下，以 256 = 16 x 16 为轴，上下两边对称位置上的等式是完全一样的。这一点，居然没有让你看出来？
       既然一样，那就只需要循环一半次数就够了呀，这个还不顺理成章？？？

jcpython2

jackz007 发表于 2022-10-22 23:38
3 楼用实例说明的为什么寻找目标数 n 因子时的枚举范围应该是 2 ~ sqrt(n) ，自以为讲解得非常 ...

老哥我对你给出的提示代码是有认真阅读，并且每字每句都看的，我还百度了各个提到的数学概念

如我上面的图片

                               
登录/注册后可看大图

我知道你想引导告诉我范围应该循环一半即可

就像 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不需要再检查


那么……那么

我在写这个回复的时候写到这里我自己纳闷，我想到哪里去？我怎么好像脑子跟手脱钩了？



=============


缓了一下

当判断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到就是素数呢


你给的提示，跟这个沾边但我又无法理解到这个点

jcpython2

数学基础差，确实吃不过来，先睡一觉，明日再挣扎

china2022

1

Stubborn

什么叫素数，除开1和本身，不能被其他数整除。
针对你的代码而言，下面这一行代码往上处理了什么数字，1，2，和偶数，被剔除。偶数剔除后，筛选的步长则设置为2

for i in range(3,n,2):

下面这行代码而言，对一个整数而言，i*i > n 后面可以不用搜锁，你不理解为什么，100可以被整除的数字包括这些[1, 2, 4, 5, 10, 20, 25, 50, 100]。

如果一个整数N可以被整除，你只需要搜索 1 ~ i * i >N ，如果i~N还存在可以被整除的数字，那么结果肯定是比I小。但是1~I的区间，程序已经搜索过。没有必要搜索。
所以综合而言，程序只需要搜索1 ~ i * i >N 范围的数字，这个区间的数字都不能被整除，那么这个数字肯定是一个素数

if i * i > n:  

jcpython2

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里面因子

那么现在我这个是 %  不是*

能用%的方式说一遍吗，谢谢

Stubborn

jcpython2 发表于 2022-10-27 16:11
经过各位老哥的热心解释，我已经基本勾勒出你们指导的原理
但你能用运算过程做一次我看看么

不明白你的问题

jcpython2

Stubborn 发表于 2022-10-24 17:48
什么叫素数，除开1和本身，不能被其他数整除。
针对你的代码而言，下面这一行代码往上处理了什么数字，1， ...

我所理解的你这段话是:判断100内是否能被整除只需要判断到10

因为100 除以1~10得出的数肯定少于100除以20~100的数,就因为后面的数除的值更少就不需要判断?为什么?

说回我的代码.

我的那行代码i * i是在判断素数途中,那么上面那个除一半就够,和这行代码有什么具体关系??



老哥我基础是真的比较差，你可以不需要继续回答的，我感觉也是有点勉强

Stubborn

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不一样，在这个过程这种，它们都代表一个情况，可以被整除。所以才说，超过一个临界值，就不需要再判断了。

上面那个除一半就够,和这行代码有什么具体关系??
是指步长吗？步长就是剔除偶数不计算在内