调试 Python 素数程序

Question

我编写了 Python 素数生成器的代码，用于生成前 100 个素数。但是，不知何故，我在输出中得到了 22、25 等非素数。我已经一遍又一遍地重新检查了几个小时，但仍然无法弄清楚我错在哪里......请帮忙！

这是我的代码：

from math import sqrt

y=[2]
x=3

while len(y)!=100:
   for i in range (2,int(round(sqrt(x)+1))):
     if x%i==0:
        x=x+1

     else:
        y.append(x)
        x=x+1
        break

print(y)

Answer 1

我会这样做；更Pythonic一点：

y = [2]
x = 3
while len(y) < 100:
    if all(x % i != 0 for i in range(2, int(round(sqrt(x) + 1)))):
        y.append(x)
    x = x + 1

print(y)

all()

功能非常有用。

这与您所做的更相似；请注意

break

声明及其作用：

from math import sqrt

y=[2]
x=3

while len(y) != 100:
    is_prime = True
    for i in range (2, int(round(sqrt(x) + 1))):
        if x % i == 0:
            x += 1
            is_prime = False
            break # this means that x is not prime and we can move on, note that break breaks only the for loop
    if is_prime:
        y.append(x)
        x += 1

print(y)

Answer 2

其他答案是正确的，但没有一个答案表明您实际上可以在

else

循环上使用

for

子句。阅读更多相关信息这里。所以你不需要

if is_prime:

声明。结果代码可能看起来像这样。

 from math import sqrt

 y = [2]
 x = 3

 while len(y) != 100:
    for i in range (2, int(round(sqrt(x) + 1))):
        if x % i == 0:
            x = x + 1
            break

    else:
        y.append(x)
        x = x + 1
print(y)

提示：

x+=1

可以代替

x=x+1

此外，作为@user2346536，您实际上可以使用一种更有效的算法来计算素数，如果您循环遍历大量数字，这将很重要。

Answer 3

else 的内容应该在 for 循环之外。在这里，一旦 x 无法被“至少一个 i”除，而不是“无法被每个 i”除，就将 x 添加到数组中

而且这种算法效率非常低。为了快速一试： https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

from math import sqrt

y=[2]
x=3

while len(y)!=100:
    prime = True
    for i in [ i for i in y if i < sqrt(x) + 1 ]:
        if x%i==0:
            prime = False
            break

    if prime:
        y.append(x)

    x=x+1


print(y)

请注意，我已经通过仅除以先前找到的素数来优化您的算法。

Answer 4

正如 user2346536 所说，你的 else 不应该在循环内。您只会查看该元素

i = 2

如何做：

from math import sqrt, ceil
prime_list = [2]
x = 2
while prime_list != 100:
    x += 1
    is_prime = True
    for element in range(2,int(ceil(sqrt(x)))):
        # if x is divided, then we go to next iteration
        if x%element == 0:
            is_prime = False
            break
    if is_prime:
        y.append(x)

Answer 5

您对数字是否素数的测试是错误的。您检查一个数字是否可以被

i

从 2 整除到

sqrt(x)

，这是正确的，但是一旦您遇到一个不是因数的数字，您就认为该数字是质数，这是不正确的。您必须检查所有数字，如果没有一个是因子，那么您可以得出结论，您的数字是质数：

from math import sqrt

y=[2]
x=3

while len(y)!=100:
    isPrime=True
    for i in range (2,int(round(sqrt(x)+1))):
        if x%i==0:
            x=x+1
            isPrime=False
            break             # See Mr Nun's answer
    if(isPrime):
        y.append(x)
        x=x+1

print(y)

正如所指出的，这不是一个非常有效的解决方案。查看@user2346536 的答案中的链接。

Answer 6

使用埃拉托斯特尼筛法规则查找素数

# Find Prime Numbers using Sieve of Eratosthenes rule
listPrime = []  #create a list and add 1 to 100 nunbers
for i in range (1, 101):
    listPrime.append (i)
print("The Numbers are: " + str(listPrime))

for i in range (2, 101):
    for j in range (i, 101): 
        z = i * j
        if (z > 100):
            break
        else:
            if z in listPrime:
                listPrime.remove(z)

print ("The Prime Numbers are: " + str(listPrime))

Answer 7

打印前一百个质数的代码：

def prime_hundred():
    prime = [2]
    num = 3
    while len(prime) < 100:
        for i in range(2, num):
            if num % i == 0:
                break
        else:
            prime.append(num)
        num += 1
    return prime


print(prime_hundred())

Answer 8

我刚刚移动了 X+=1 并在数字不是素数时使用了“break”。

from math import sqrt

y=[2]
x=2

while len(y)!=100:
   x+=1
   if x%2 ==0: continue # no evens
   for i in range (3,int(round(sqrt(x)+1))):
       if x%i==0: break
   else: # break skips this
       y.append(x)
print(y)