Python素数列表重复bug

Question

尝试创建一个程序，在一定的区间内列出质数（必须在1到500之间），所以不允许用户输入。这是我的代码：

list=[]
for num in range(1, 500):
    if num > 1:
        for i in range(2, num):
            if (num % i) == 0:
                break
            else:
                list.append(str(num))
print(','.join(list))

然而，当我运行这段代码时，列表中有些质数重复出现多次，使得列表比应该的要长得多。我该如何解决这个问题？感谢您提前的帮助。

- AsmtelRadler

---

问题在于，在找到一个能够整除 num 的数字 i 之前，num 将被添加到列表中。很明显，您将在列表中多次包含每个质数。事实上，如果 n 是素数，则您将在列表中有 n-2 次出现 n。您也会在列表中包含所有奇数。 - innoSPG

Answer 1

在你检查所有可能的除数之后，你只想将这个数字添加到质数列表中。这意味着你只能在for循环完成后才能添加它。

一个好的方法是使用for循环上的可选else子句。

循环语句可以有一个else子句；当循环通过遍历列表（使用for）或条件变为假（使用while）而终止时，它会被执行，但当循环被break语句终止时不会执行。

你可以通过仅检查已经找到的质数的模数来改进这个函数。由于所有非质数都有质数因子，你只需要检查一个数字是否能被较小的质数整除来确定它是否是质数。

primes = []
for i in range(2, 501):
    for p in primes:
        if i % p == 0:
            break
    else:
        primes.append(i)

- Brendan Abel

---

谢谢，那帮助我更好地理解了。 - AsmtelRadler

Answer 2

在循环中：

for i in range(2, num):
    if (num % i) == 0:
        break
    else:
        list.append(str(num))

你正在每个 i 上附加质数一次。else 应该与 for 对齐：

for i in range(2, num):
    if (num % i) == 0:
        break
else:   # note: different indentation!
    list.append(str(num))

在Python中，循环可以有一个else子句，仅当循环内没有执行break时才会执行。它们可以用于避免许多情况下的布尔标志。

因此，代码如下：

found = False
for x in iterator:
    if predicate(x):
        found = True
        break

if not found:
    # do default action

可以被替换为：

for x in iterator:
    if predicate(x):
        break
else:
    #do default action

- Bakuriu

---

循环的else是我不知道的好东西。但需要确保的是，原帖作者不想包括1。在这种情况下，他必须从外部循环中排除1，这本来就是多余的。 - innoSPG

@innoSPG OP的代码已经包含了一个if num>1，所以1根本不会被检查。 - Bakuriu

Answer 3

确保每个数字只添加一次。

问题在于，直到找到一个能够整除num的数字i之前，num会被添加到列表中。很明显，你会在列表中多次拥有每个质数。事实上，如果n是质数，那么你将在列表中拥有n-2次n。你还将在列表中拥有所有奇数。

只有偶数不会出现在列表中，因为你测试可整除性的第一个数字是2，而2可以整除所有偶数。

在不改变算法太多的情况下，你可以引入一个默认设置为True的标志isPrime，每当你找到一个能够整除num的数字i时，在退出循环之前将isPrime设置为True。你的程序变成了：

list=[]
for num in range(1, 500):
    if num > 1:
        isPrime=True
        for i in range(2, num):
            if (num % i) == 0:
                isPrime = False
                break
        if isPrime:
            list.append(str(num))
print(','.join(list))

- innoSPG