为什么我的素数算法需要在for循环中断？

我写了一个算法，用前1000个素数填充列表。为什么我的素数算法需要在for循环中断？

当我像这样运行它时，它会用一些不是素数的数字填充列表。

def is_prime(): 
    primes = [2] 
    a = 0 
    x = 3 
    while a < 999: 
     for i in range(2, x): 
      if (x % i) == 0: 
       x += 2 
       break 
     else: 
      primes.append(x) 
      a += 1 
      x += 2 
    return primes 


print is_prime()

来源

2014-01-13 user3188950

请妥善缩进代码。 –

也许不会发布完全相同的代码？ –

你没有想到的是什么值？ – Christian

[为什么这]需要循环的休息？

让我引用this tutorial you might want to look at：

循环可以有一个其他条款;当循环终止时通过穷举的列表（用for）[...]，但不是当循环终止时break语句。

这意味着，在您的while -loop，

primes.append(x) 
a += 1 
x += 2

如果for -loop已遍历所有i in range(2, x)，从来没有一次遇到break时，才会执行。（这意味着，没有发现x的除数）

没有的break声明上面的代码将在的while -loop的每一次迭代执行。因此，如果没有break声明，则只需在每次找到x的除数时宣布2到x，并声明只要到达range(2, x)的末尾x就是质数（请注意，在范围表达式中，在开始添加之前它是原始的x2）。这似乎适用于小数字，但与检查x是否有任何除数不同。

来源

2014-01-13 04:53:31 Lmis

你的算法似乎工作。

例如，比较一个更standard approach：

def rwh_primes(n): 
    """ Returns a list of primes < n """ 
    sieve = [True] * n 
    for i in xrange(3,int(n**0.5)+1,2): 
     if sieve[i]: 
      sieve[i*i::2*i]=[False]*((n-i*i-1)/(2*i)+1) 
    return [2] + [i for i in xrange(3,n,2) if sieve[i]] 

p0 = is_prime() # OP's code 
p1 = rwh_primes(7920) 

print p0==p1 # prints True, so the lists are equal

来源

2014-01-13 05:26:13 tom10

为什么我的素数算法需要在for循环中断？

回答

相关问题