用Python计算1000素数

Question

我试图找到1000个素数，并试图做到这一点没有作弊记忆或其他代码。你能告诉我我的代码是正确的还是完全不正确的吗？你知道吗

primes = []
num = 3
while (len(primes)) < 1000:
    if num / 2 == 0:
        num = num + 1
    else:
        x = num - 1
        for z in range(2,x):
            if num % z == 0 :
                num = num + 1
            else:
                primes.append(num)
                num = num + 1

print primes[1000]

Answer 1

你有一些问题（num / 2 == 0应该是num % 2 == 0）¹，但实际上，使用continue和break会很有帮助。e、 g

for z in range(2,x):  # xrange would be a performance win on python2.x
    if num % z == 0 :
        num = num + 1
    else:
        primes.append(num)
        num = num + 1

在这个循环中，您可能会发现自己在不断地增加num很多次。实际上，您只需要将其递增一次（以转到下一个数字）。所以在这里你需要在你增加它之后break。另外，else语句需要在for循环中：

for z in range(2, x):
    if num % z == 0:
        break  # exit the for loop, don't execute `else` clause.
else:
    # only executes if `break` was never encountered.
    primes.append(num)

# This happens no matter what and should only happen once
# Might as well pull it out of the loop.
num += 1

---

<sup>1检查2的可除性是没有用的，这是循环的第一次迭代。如果您使用了xrange（对于python2.x）和break（如我所述），那么这种优化（可能）是不值得的。

旁白：您实际上不需要运行从2到N - 1的循环，您实际上可以不必运行从2到int(math.sqrt(N))的循环，这会使这更高效：-）尽管仍然不是您所能做到的最好的。。。Sieve of Eratosthenes是另一种更有效的算法，可能还有比这更好的方法（尽管我不是这方面的专家）</sup>