weixin_54282146
weixin_54282146
2021-03-30 20:26
采纳率: 100%
浏览 455

python利用while循环求2到100内的素数,求大神指点

i = 2
while(i < 100):
   j = 2
   while(j <= (i/j)):
      if not(i%j): break
      j = j + 1
   if (j > i/j) : print(i, end="  ")
   i = i + 1

逻辑有点理不清

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

4条回答 默认 最新

  • technologist_16
    已采纳
    # 外层循环 i 从2循环到99
    i = 2
    while(i < 100):
       # 内层循环 j 从2循环到根号 i
       j = 2
       while(j <= (i/j)): # j <= (i/j) 等效于 j*j <= i 也就等于 j <= 根号 i
          if not(i%j): break #判断如果i可以被j整除,则提前跳出j的循环
          j = j + 1
       #如果j > i/j判断为真表示正常循环结束,i没有被j整除,i是素数。 否则就是提前跳出j循环的,i有被j整除,i不是素数。
       if (j > i/j) : print(i, end="  ")
       i = i + 1
    
    点赞 1 评论
  • technologist_15
    CSDN专家-三岁丫 2021-03-30 20:48
    # 素数从 2 开始找
    i = 2
    while(i < 100):
       j = 2
       # 为什么是 j <= i/j 例如 i = 20,那么可能整除的组合就是 2 * 10、4 * 5、5 * 4、10 * 2。可以发现组合是重复的了一次的
       # 所以只要 j <= i/j 就能试完所有的情况
       while(j <= (i/j)):
       	  # 如果找到能整除的,说明不是一个素数,直接 break
          if not(i%j): break
          j = j + 1
       # 如果 j > i/j 说明不是被 break 出来的,那么它是一个素数
       if (j > i/j) : print(i)
       i = i + 1
    点赞 2 评论
  • xufive
    天元浪子 2021-03-30 22:24

    判断一个数n是否是素数,通常从第1个素数2开始,如果n能被2整除,则n不是素数,否则,再用下一个素数3去检验,直到素数大于n的平方根时仍然不能被整除,则n为素数。题主的代码中,j每次递增1而不是使用素数表,存在逻辑漏洞。

    下面是根据上述思路写成的代码:

    >>> i, prime = 2, [2]
    >>> while i < 100:
    	is_prime = True # 假设i是素数
    	for j in prime: # 遍历素数表
    		if not i%j: # 如果i被当前素数整除
    			is_prime = False # 则i不是素数
    			break # 退出遍历素数表
    		elif j > i/j: 如果当前素数大于i的平方根
    			break # 退出素数循环
    	if is_prime: # 如果i是素数
    		prime.append(i) # 则加入素数表
    	i += 1 # i加1
    
    	
    >>> prime
    [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]
    

    如果查找素数的范围不是很大,下面的写法更简洁:

    >>> i, prime = 2, [2]
    >>> while i < 100:
    	for j in prime:
    		if not i%j:
    			break
    	else:
    		prime.append(i)
    	i += 1
    
    	
    >>> prime
    [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]

    不过,上面的两种写法效率都不高,查找1亿以内的素数,大概20分钟跑不完。要想加速,需要改变思路,同时要用到NumPy。我有篇博客介绍的方法,可以在3秒中找出1亿内的素数,感兴趣可以参考下。https://xufive.blog.csdn.net/article/details/102892049

    点赞 1 评论
  • QA_Assistant
    有问必答小助手 2021-03-31 11:02

    您好,我是有问必答小助手,你的问题已经有小伙伴为您解答了问题,您看下是否解决了您的问题,可以追评进行沟通哦~

    如果有您比较满意的答案 / 帮您提供解决思路的答案,可以点击【采纳】按钮,给回答的小伙伴一些鼓励哦~~

    ps:问答VIP仅需29元,即可享受5次/月 有问必答服务,了解详情>>>https://vip.csdn.net/askvip?utm_source=1146287632

    点赞 评论

相关推荐