这段求质数看不懂……已更新代码………………………………
本帖最后由 jcpython2 于 2022-9-25 17:22 编辑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但结果并未触发
是这样 质数判断的话要看这个数是否有 1 和 它自己 的别的因数
而我们知道, 因数是成对出现的 , 比如 18
1, 2, 3, 6, 9, 18 对吧
我们给它两两分组 :
(1, 18) (2, 9) (3, 6) 这样有什么好处呢 ?
减少判断次数 , 由于每一对的数乘积都是 n , 所以最大只需判断 2 - 根号n 的数字
如果这个区间内有可以整除的 , 就直接返回不是
否则 , 就是质数 本帖最后由 jackz007 于 2022-9-24 18:22 编辑
循环终止条件，比如，当 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 作为因子再多枚举一遍。 柿子饼同学 发表于 2022-9-24 17:52
是这样 质数判断的话要看这个数是否有 1 和 它自己 的别的因数
而我们知道, 因数是成对出现的 , 比如 18
...
数学基础不好，现在不单数学没弄清，运行逻辑也乱了 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 于 2022-9-25 18:24 编辑
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:\\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:\\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
与前面的代码相比，结果相同，但是，效率可能要低一些 jackz007 发表于 2022-9-25 18:11
运行实况：
老哥你的代码很牛解了我的题目，但没有解到我的疑问 我还是对以下有所疑问
n循环到3后会触发n % i ==0但结果并未触发
n: 3 进入条件三
3 不满足条件123 这个代码已经很简单了，而且，我也注释得很详细了，如果还有疑问，我已经没办法了，我只能说，你天份不够，太吃力，放弃吧！ jackz007 发表于 2022-9-25 19:51
这个代码已经很简单了，而且，我也注释得很详细了，如果还有疑问，我已经没办法了，我只能说，你天 ...
好吧 看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开始可以吗 简单滴滴 发表于 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 的初步筛选 ...
了解,了解 简单滴滴 发表于 2022-9-26 13:05
看range(3,3,2)
当n是3的时候i是空的,获取不到值的
我排查漏了最基础的一步，range(3,3)根本不会触发3出来，而我一直纠结 3 %3 ==0
所以我找到错处了，已经解决了问题
页:
[1]