python-3.x - 仅使用循环和 if 语句打印素数

Question

这段代码有什么问题？

import math
y=1
z=y
while z>= 1 and z<1000 :
    z= 2*y + 1
    y=y+1
    for a in range (2,int(math.sqrt(z) + 1)):
        if z%a != 0:
            print(z)
        else:
            break

这里有什么问题？我的输出中也不断得到复合数。

Answer 1

您正在打印一个数字，即使它不能被一个数字整除但可以被另一个数字整除。

打印应该在循环之外。

 import math
 y=1
 z=y
 while z>= 1 and z<1000 :
      z= 2*y + 1
      y=y+1
      flag=0
      for a in range (2,int(math.sqrt(z) + 1)):
          if z%a == 0:
              flag=1
              break
      if flag==0:
          print z

改进算法的另一种方法是移动 6 的倍数并检查数字，multipleofsix-1这multiple of six+1会给你带来更好的效率。除了 2 和 3 之外，所有其他素数都可以在该范围内找到。

进一步的改进将需要您维护一个数组并存储所有先前的素数，并且只除以您正在检查的数字的平方根以下的所有素数。

还有更好的即兴创作，例如 Eratosthenes 和 Atkins 的筛子，但这些是您可以实现的最基本的。

Answer 2

要使z成为素数，必须是不存在任何数a使得a是z2 <= a <= sqrt(z)的因数的情况。我会将您的代码更改为：

import math
y=1
z=y
while z>= 1 and z<1000 :
    z= 2*y + 1
    y=y+1
    if all(z%a != 0 for a in range (2,int(math.sqrt(z) + 1))):
        print(z)