[已解决]多层循环问题

寒园

看到大家都在讨论欧拉练习中的求100W以内的神奇质数问题，无奈鄙人才疏学浅，无法单独写出答案，因而鄙人退而求次，求100以内的所有质数，用了两个循环，代码如下

1. zhishu = []
   
2. for each in range(2,100):
   
3.     for i in range(2,int(each)):
   
4.         if each % i != 0:
   
5.             zhishu.append(each)
   
6.             break         
   
7. print(zhishu)

复制代码

但是得出的结果却是如下

1. [3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99]

复制代码

很显然这些数中有些不是质数，通过degbug看到，问题原因在第二个循环for i in range(2,int(each))，在该循环中，i的第一个值为2，如果碰到each的值为5，碰巧没有问题，但是如果each为9，虽然i等于2时无法整除，但是当i为3时可以整除，而第一次each % i 刚好不等于0，所以满足了判断条件’

而如果不写break，又有其他问题

因此这段代码要如何修改？就是要实现第二个循环中从（2，each）连续取值进行除法

最佳答案

月排行榜 / 总排行榜

冬雪雪冬

2016-9-18 22:10:19

修改了一下：

1. zhishu = []
   
2. for each in range(2,100):
   
3.     for i in range(2, each):
   
4.         if each % i == 0:
   
5.             break
   
6.     else:
   
7.         zhishu.append(each)
   
8. print(zhishu)
   

复制代码

程序还有一些可以优化的地方。

跳转到最佳答案楼层

冬雪雪冬

修改了一下：

1. zhishu = []
   
2. for each in range(2,100):
   
3.     for i in range(2, each):
   
4.         if each % i == 0:
   
5.             break
   
6.     else:
   
7.         zhishu.append(each)
   
8. print(zhishu)
   

复制代码

程序还有一些可以优化的地方。

人zai旅途

冬雪雪冬 发表于 2016-9-18 22:10
修改了一下：

程序还有一些可以优化的地方。

楼主问题还没学到。。大神有空看看我的问题啊列表分片那个

寒园

冬雪雪冬 发表于 2016-9-18 22:10
修改了一下：

程序还有一些可以优化的地方。

说下思路，我去动手优化下

冬雪雪冬

寒园 发表于 2016-9-18 22:20
说下思路，我去动手优化下

在外循环除了2以外，质数只能是奇数，所以循环的步长可以为2，这样计算量可以减半。
在内循环只要判断到数值的平方根即可，如11只需判断到3。
如果不能被3整除肯定不能被6，9，12，15...整除。

SixPy

http://bbs.fishc.com/forum.php?mod=redirect&goto=findpost&ptid=75901&pid=2657258

这里有个10亿之内素数的例子

树精树蛙

冬雪雪冬 发表于 2016-9-18 22:10
修改了一下：

程序还有一些可以优化的地方。

第6步的else没明白~~~~求解释

冬雪雪冬

树精树蛙 发表于 2016-9-18 22:59
第6步的else没明白~~~~求解释

for循环和while循环都可以跟else。即循环正常结束，而不是break结束则执行else的语句。
此例中第3行的for循环如果没有break即不被其他数整除则是质数，将其加入列表。

树精树蛙

冬雪雪冬 发表于 2016-9-18 23:03
for循环和while循环都可以跟else。即循环正常结束，而不是break结束则执行else的语句。
此例中第3行的fo ...

好的，谢谢

SixPy

SixPy 发表于 2016-9-18 22:31
http://bbs.fishc.com/forum.php?mod=redirect&goto=findpost&ptid=75901&pid=2657258

这里有个10亿之内 ...

• def P10(n):
•     r = int(n**0.5)
•     x=100
•     #assert r*r <= n and (r+1)**2 > n
•     V = [n//i for i in range(1,r+1)]
•     V += list(range(V[-1]-1,0,-1))
•     S = {i:i*(i+1)//2-1 for i in V}
•     for p in range(2,r+1):
•         if S[p] > S[p-1]:  # p is prime
•             if x>0:
•                 print(p)
•                 x-=1
•             sp = S[p-1]  # sum of primes smaller than p
•             p2 = p*p
•             for v in V:
•                 if v < p2: break
•                 S[v] -= p*(S[v//p] - sp)
•     return S[n]
• #N = 200*10**4
• N = 1000000000
• from time import time as tm
• t=tm()
• x = P10(N)
• t=tm()-t
• print (x,t)
• input()
  

寒园

SixPy 发表于 2016-9-19 17:07

代码看起来很高大上

SixPy

寒园 发表于 2016-9-19 20:35
代码看起来很高大上

反正不是我写的