python - 在 python 中生成素数 : how is my logic wrong

Question

我将在秋季开始一个计算机科学项目，并且在开始之前我正在努力建立我的编程能力。

我正在解决 MIT OCW 6.0 问题，第一个问题是生成第 1000 个素数。显然，我想生成自己的代码，所以我想知道我的逻辑哪里出了问题。

counter = 1
primes = [2]
n = 3
while counter < 1000:
    for i in range(2, n):
        if n % i == 0:
        break
        else:
            primes.append(n)
            counter = counter + 1
    n = n + 1

print primes

你们太棒了，所以我不会在这里解释每一行，但我的逻辑要点是我希望这个循环从 n 开始。如果 n 是质数，则将其添加到列表中，并向计数器添加 1，如果不是，则继续处理下一个数字。最后，打印列表，以第 1000 个素数结尾。

看，我知道这是“蛮力”，我知道有筛子和更复杂的逻辑，但我希望它以这种方式工作。现在，我得到了很多重复的数字，但没有接近第 1000 个素数。

谢谢大家。这是我的第一个问题，但我相信还会有更多问题。

Answer 1

你的逻辑是正确的，但你的区 block 不是。中断应该缩进(在 if n % i 下)，而 else 应该不缩进，所以它是 for 循环的 else - 即只有当没有一个素数是它的因子时才会添加数字，而不是每个素数的一次就是它的因子。

counter = 1
primes = [2]
n = 3
while counter < 1000:
    for i in range(2, n):
        if n % i == 0:
           break
    else:
        primes.append(n)
        counter = counter + 1
    n = n + 1

print primes

您只需将 n 除以(到目前为止的素数列表)即可节省时间，而不用将所有数字除以 - 只需将 range(2, n) 替换为 primes