[已解决]这段求质数看不懂……已更新代码………………………………

jcpython2

def isprime(n):
    if n <= 1 or n % 2 == 0 and n !=2:     #负数或者同时满足不是2而且还%0则非质数
        return False
    elif n ==2:                             #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(int(input())):
    if(isprime(i)):
        print(i,end=" ")

看不懂以下这段

for i in range(3,n,2):
            if n % i == 0:
                return False
            if i * i > n:
                break

如果代入n为3那么  n % i == 0 也就是 3% 3 == 0是成立的但成立后返回了false，实际结果返回true


i * i  > n
这段完全不懂作用


以下是我排查弄懂添加了的代码，但还是不懂

def isprime(n):
    if n <= 1 or n % 2 == 0 and n !=2:     #负数或者同时满足不是2而且还%0则非质数
        print(n,'触发条件1')
        return False
    elif n ==2:                             #2为质数
        print(n,'满足条件2')
        return True
    else:
        print('n:',n,'进入条件三')
        for i in range(3,n,2):
            print('条件3-1 i&n:',i,n)
            if n % i == 0:
                print('触发条件3-1,n%i==0',n,i)
                return False
            if i * i > n:
                print('触发条件3-2')
                break
    print(n,'不满足条件123,返回true')
    return True
for i in range(int(input())):
    if(isprime(i)):
        print(i,end=" ")

5
0 触发条件1
1 触发条件1
2 满足条件2
2 n: 3 进入条件三       
3 不满足条件123,返回true
3 4 触发条件1

我预期中n循环到3后会触发  n % i ==0但结果并未触发

最佳答案

月排行榜 / 总排行榜

jackz007

2022-9-25 18:11:32

jcpython2 发表于 2022-9-25 17:15
弄了好久还是不懂，唉~~~

先不说其他，我一步一步来

def isprime(n) :
    r = False                                      # n 缺省不是素数
    if n > 1:
        if n % 2 and n % 3 and n % 5 and n % 7:    # 如果 n 不能同时被 2、3、5、7 整除，满足条件的 n 至少是 11
            i , r = 3 , True                       # 假定 n 是素数，i 从 3 开始枚举 n 的可能因子
            while i * i < n + 1:                   # i 的枚举范围是 3 ～ sqrt(n)
                if n % i == 0:                     # 找到了因子
                    r = False                      # 否定之前 n 是素数的假设
                    break                          # 结束循环
                i += 2                             # i 以 2 为步长继续枚举
        elif n == 2 or n == 3 or n == 5 or n == 7: # 如果 n 就是 2、3、5、7 本身，那么，不用计算，它肯定就是素数
            r = True
    return r

c = 0
for i in range(int(input())):
    if(isprime(i)):
        if c:
            print('\t' , end = '' , sep = '')
        print(i , end = ' ' , sep = '')
        c += 1

        运行实况：

D:\[00.Exerciese.2022]\Python>python x.py
100
2       3       5       7       11      13      17      19      23      29
31      37      41      43      47      53      59      61      67      71
73      79      83      89      97
D:\[00.Exerciese.2022]\Python>

        当然，isprime() 也可以这样来定义：

def isprime(n) :
    r = False
    if n > 1:
        for i in range(3 , n , 2):    # i 的枚举范围 3 ～ n - 1
            if n % i == 0:
                break
        else:
            r = True
    return r

        与前面的代码相比，结果相同，但是，效率可能要低一些

跳转到最佳答案楼层

柿子饼同学

是这样 质数判断的话要看这个数是否有 1 和 它自己 的别的因数
而我们知道, 因数是成对出现的 , 比如 18
1, 2, 3, 6, 9, 18 对吧
我们给它两两分组 :
(1, 18) (2, 9) (3, 6) 这样有什么好处呢 ?
减少判断次数 , 由于每一对的数乘积都是 n , 所以最大只需判断 2 - 根号n 的数字
如果这个区间内有可以整除的 , 就直接返回不是
否则 , 就是质数

jackz007

      循环终止条件，比如，当 n = 83 时，枚举 i  到 10 就终止。
      假如 a x b = 81，那么，9 就是因数的分界线，当 a = 9 时，有 a = b；当 a < 9 时，有 a < b，当 a > 9 时，有 a > b，因为乘法满足交换律，a x b 和 b x a 是相等的，所以，对于 n ，最多只需要枚举到因数的一半，也就是 i = sqrt(n) 为止就可以了，继续枚举没有意义。
      例如，对于 n = 81，只要枚举了 i = 3，3 x 27 = 81，就足矣，没有必要再把 i = 27，81 = 27 x 3 作为因子再多枚举一遍。

jcpython2

柿子饼同学 发表于 2022-9-24 17:52
是这样 质数判断的话要看这个数是否有 1 和 它自己 的别的因数
而我们知道, 因数是成对出现的 , 比如 18
...

数学基础不好，现在不单数学没弄清，运行逻辑也乱了

jcpython2

jackz007 发表于 2022-9-24 18:00
循环终止条件，比如，当 n = 83 时，枚举 i  到 10 就终止。
      假如 a x b = 81，那么，9 就是 ...

弄了好久还是不懂，唉~~~

先不说其他，我一步一步来
以下我加了备注的代码，我始终不明白为啥 n=3的时候没有触发

if n % i == 0:
                print('触发条件3-1,n%i==0',n,i)
                return False

def isprime(n):
    if n <= 1 or n % 2 == 0 and n !=2:     #负数或者同时满足不是2而且还%0则非质数
        print(n,'触发条件1')
        return False
    elif n ==2:                             #2为质数
        print(n,'满足条件2')
        return True
    else:
        print('n:',n,'进入条件三')
        for i in range(3,n,2):
            print('条件3-1 i&n:',i,n)
            if n % i == 0:
                print('触发条件3-1,n%i==0',n,i)
                return False
            if i * i > n:
                print('触发条件3-2')
                break
    print(n,'不满足条件123,返回true')
    return True
for i in range(int(input())):
    if(isprime(i)):
        print(i,end=" ")

5
0 触发条件1
1 触发条件1
2 满足条件2
2 n: 3 进入条件三       
3 不满足条件123,返回true
3 4 触发条件1

jackz007

jcpython2 发表于 2022-9-25 17:15
弄了好久还是不懂，唉~~~

先不说其他，我一步一步来

def isprime(n) :
    r = False                                      # n 缺省不是素数
    if n > 1:
        if n % 2 and n % 3 and n % 5 and n % 7:    # 如果 n 不能同时被 2、3、5、7 整除，满足条件的 n 至少是 11
            i , r = 3 , True                       # 假定 n 是素数，i 从 3 开始枚举 n 的可能因子
            while i * i < n + 1:                   # i 的枚举范围是 3 ～ sqrt(n)
                if n % i == 0:                     # 找到了因子
                    r = False                      # 否定之前 n 是素数的假设
                    break                          # 结束循环
                i += 2                             # i 以 2 为步长继续枚举
        elif n == 2 or n == 3 or n == 5 or n == 7: # 如果 n 就是 2、3、5、7 本身，那么，不用计算，它肯定就是素数
            r = True
    return r

c = 0
for i in range(int(input())):
    if(isprime(i)):
        if c:
            print('\t' , end = '' , sep = '')
        print(i , end = ' ' , sep = '')
        c += 1

        运行实况：

D:\[00.Exerciese.2022]\Python>python x.py
100
2       3       5       7       11      13      17      19      23      29
31      37      41      43      47      53      59      61      67      71
73      79      83      89      97
D:\[00.Exerciese.2022]\Python>

        当然，isprime() 也可以这样来定义：

def isprime(n) :
    r = False
    if n > 1:
        for i in range(3 , n , 2):    # i 的枚举范围 3 ～ n - 1
            if n % i == 0:
                break
        else:
            r = True
    return r

        与前面的代码相比，结果相同，但是，效率可能要低一些

jcpython2

jackz007 发表于 2022-9-25 18:11
运行实况：

老哥你的代码很牛解了我的题目，但没有解到我的疑问 我还是对以下有所疑问

n循环到3后会触发  n % i ==0但结果并未触发

n: 3 进入条件三      
3 不满足条件123

jackz007

        这个代码已经很简单了，而且，我也注释得很详细了，如果还有疑问，我已经没办法了，我只能说，你天份不够，太吃力，放弃吧！

jcpython2

jackz007 发表于 2022-9-25 19:51
这个代码已经很简单了，而且，我也注释得很详细了，如果还有疑问，我已经没办法了，我只能说，你天 ...

好吧

简单滴滴

看range(3,3,2)

[i for i in range(3,3,2)]
[]

当n是3的时候  i是空的,获取不到值的
直接跳过else 进入下一步的 return True
写成这样你看下可以明白吗

n = 3
if n <= 1 or n % 2 == 0 and n !=2:     #负数或者同时满足不是2而且还%0则非质数
    print(1)
elif n ==2:                             #2为质数
    print(2)
else:
    for i in range(3,n,2):
        if n % i == 0:
            print(3)
        if i * i > n:
            break
print(4)

简单滴滴

jackz007 发表于 2022-9-25 18:11
运行实况：

            i , r = 3 , True                       # 假定 n 是素数，i 从 3 开始枚举 n 的可能因子

这个为什么要从3开始呢,11开始可以吗

jackz007

简单滴滴 发表于 2022-9-26 13:37
这个为什么要从3开始呢,11开始可以吗

      当然可以，因为在 2 ~ 10 的范围内，哪些是素数是有确切结论的。而且，经过 2、3、5、7 的初步筛选，可以大大减少因子的枚举数量。

简单滴滴

jackz007 发表于 2022-9-26 13:46
当然可以，因为在 2 ~ 10 的范围内，哪些是素数是有确切结论的。而且，经过 2、3、5、7 的初步筛选 ...

了解,了解

jcpython2

简单滴滴 发表于 2022-9-26 13:05
看range(3,3,2)

当n是3的时候  i是空的,获取不到值的

我排查漏了最基础的一步，range(3,3)根本不会触发3出来，而我一直纠结 3 %3 ==0

所以我找到错处了，已经解决了问题