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

jcpython2

1. 
   
2. def isprime(n):
   
3.     if n <= 1 or n % 2 == 0 and n !=2:     #负数或者同时满足不是2而且还%0则非质数
   
4.         return False
   
5.     elif n ==2:                             #2为质数
   
6.         return True
   
7.     else:
   
8.         for i in range(3,n,2):
   
9.             if n % i == 0:
   
10.                 return False
    
11.             if i * i > n:
    
12.                 break
    
13.     return True
    
14. for i in range(int(input())):
    
15.     if(isprime(i)):
    
16.         print(i,end=" ")

复制代码

看不懂以下这段

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

复制代码

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


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


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

1. def isprime(n):
   
2.     if n <= 1 or n % 2 == 0 and n !=2:     #负数或者同时满足不是2而且还%0则非质数
   
3.         print(n,'触发条件1')
   
4.         return False
   
5.     elif n ==2:                             #2为质数
   
6.         print(n,'满足条件2')
   
7.         return True
   
8.     else:
   
9.         print('n:',n,'进入条件三')
   
10.         for i in range(3,n,2):
    
11.             print('条件3-1 i&n:',i,n)
    
12.             if n % i == 0:
    
13.                 print('触发条件3-1,n%i==0',n,i)
    
14.                 return False
    
15.             if i * i > n:
    
16.                 print('触发条件3-2')
    
17.                 break
    
18.     print(n,'不满足条件123,返回true')
    
19.     return True
    
20. for i in range(int(input())):
    
21.     if(isprime(i)):
    
22.         print(i,end=" ")

复制代码

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

复制代码

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

最佳答案

月排行榜 / 总排行榜

jackz007

2022-9-25 18:11:32

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

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

1. def isprime(n) :
   
2.     r = False                                      # n 缺省不是素数
   
3.     if n > 1:
   
4.         if n % 2 and n % 3 and n % 5 and n % 7:    # 如果 n 不能同时被 2、3、5、7 整除，满足条件的 n 至少是 11
   
5.             i , r = 3 , True                       # 假定 n 是素数，i 从 3 开始枚举 n 的可能因子
   
6.             while i * i < n + 1:                   # i 的枚举范围是 3 ～ sqrt(n)
   
7.                 if n % i == 0:                     # 找到了因子
   
8.                     r = False                      # 否定之前 n 是素数的假设
   
9.                     break                          # 结束循环
   
10.                 i += 2                             # i 以 2 为步长继续枚举
    
11.         elif n == 2 or n == 3 or n == 5 or n == 7: # 如果 n 就是 2、3、5、7 本身，那么，不用计算，它肯定就是素数
    
12.             r = True
    
13.     return r
    
14. 
    
15. c = 0
    
16. for i in range(int(input())):
    
17.     if(isprime(i)):
    
18.         if c:
    
19.             print('\t' , end = '' , sep = '')
    
20.         print(i , end = ' ' , sep = '')
    
21.         c += 1

复制代码

        运行实况：

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

复制代码

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

1. def isprime(n) :
   
2.     r = False
   
3.     if n > 1:
   
4.         for i in range(3 , n , 2):    # i 的枚举范围 3 ～ n - 1
   
5.             if n % i == 0:
   
6.                 break
   
7.         else:
   
8.             r = True
   
9.     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的时候没有触发

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

复制代码

1. def isprime(n):
   
2.     if n <= 1 or n % 2 == 0 and n !=2:     #负数或者同时满足不是2而且还%0则非质数
   
3.         print(n,'触发条件1')
   
4.         return False
   
5.     elif n ==2:                             #2为质数
   
6.         print(n,'满足条件2')
   
7.         return True
   
8.     else:
   
9.         print('n:',n,'进入条件三')
   
10.         for i in range(3,n,2):
    
11.             print('条件3-1 i&n:',i,n)
    
12.             if n % i == 0:
    
13.                 print('触发条件3-1,n%i==0',n,i)
    
14.                 return False
    
15.             if i * i > n:
    
16.                 print('触发条件3-2')
    
17.                 break
    
18.     print(n,'不满足条件123,返回true')
    
19.     return True
    
20. for i in range(int(input())):
    
21.     if(isprime(i)):
    
22.         print(i,end=" ")

复制代码

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

复制代码

jackz007

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

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

1. def isprime(n) :
   
2.     r = False                                      # n 缺省不是素数
   
3.     if n > 1:
   
4.         if n % 2 and n % 3 and n % 5 and n % 7:    # 如果 n 不能同时被 2、3、5、7 整除，满足条件的 n 至少是 11
   
5.             i , r = 3 , True                       # 假定 n 是素数，i 从 3 开始枚举 n 的可能因子
   
6.             while i * i < n + 1:                   # i 的枚举范围是 3 ～ sqrt(n)
   
7.                 if n % i == 0:                     # 找到了因子
   
8.                     r = False                      # 否定之前 n 是素数的假设
   
9.                     break                          # 结束循环
   
10.                 i += 2                             # i 以 2 为步长继续枚举
    
11.         elif n == 2 or n == 3 or n == 5 or n == 7: # 如果 n 就是 2、3、5、7 本身，那么，不用计算，它肯定就是素数
    
12.             r = True
    
13.     return r
    
14. 
    
15. c = 0
    
16. for i in range(int(input())):
    
17.     if(isprime(i)):
    
18.         if c:
    
19.             print('\t' , end = '' , sep = '')
    
20.         print(i , end = ' ' , sep = '')
    
21.         c += 1

复制代码

        运行实况：

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

复制代码

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

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

复制代码

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

jcpython2

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

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

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

复制代码

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

jackz007

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

jcpython2

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

好吧

简单滴滴

看range(3,3,2)

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

复制代码

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

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

复制代码

简单滴滴

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

1.             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

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