Python素数检查器

Question

我一直在尝试编写一个将输入数字的程序，并检查它是否是质数。如果数字实际上是质数，那么到目前为止我编写的代码可以完美地工作。如果该数字不是质数，则它的行为很奇怪。我想知道是否有人可以告诉我代码的问题所在。

a=2

num=13

while num > a :

  if num%a==0 & a!=num:

    print('not prime')

    a=a+1

  else:

    print('prime')

    a=(num)+1

输入24时给出的结果是：不是素数不是素数不是素数素数

我将如何在每个奇数而不是每个偶数的素数上修复报告素数的错误

Answer 1

一旦知道数字不是素数，就需要停止迭代。break一旦找到质数就添加一个，退出while循环。只需对代码进行最少的更改即可使其工作：a=2num=13while num > a :  if num%a==0 & a!=num:    print('not prime')    break  i += 1else: # loop not exited via break  print('prime')您的算法等效于：for a in range(a, num):    if a % num == 0:        print('not prime')        breakelse: # loop not exited via break    print('prime')如果将其放入函数中，则可以免除breakfor-else：def is_prime(n):    for i in range(3, n):        if n % i == 0:            return False    return True即使您要像这样强力求素，也只需要迭代到的平方根即可n。另外，您可以跳过测试2之后的偶数。这些建议如下：import mathdef is_prime(n):    if n % 2 == 0 and n > 2:         return False    for i in range(3, int(math.sqrt(n)) + 1, 2):        if n % i == 0:            return False    return True请注意，此代码不能正确处理0，1和负数。通过all与生成器表达式一起使用来替换for循环，我们使此过程更简单。import mathdef is_prime(n):    if n % 2 == 0 and n > 2:         return False    return all(n % i for i in range(3, int(math.sqrt(n)) + 1, 2))

Answer 2

您的代码存在两个主要问题：在指定一个非素数之后，即使您已经知道它不是素数，也要继续检查其余除数，这可能导致它在打印“非素数”之后打印“素数”。提示：使用“ break”语句。在检查所有需要检查的除数之前，请指定一个数字质数，因为您正在循环内打印“质数” 。因此，您会多次获得“素数”，对于每个除数不均等地进入被测数的除数。提示：else仅在循环退出而不会中断的情况下，才在循环中使用子句以显示“素数”。效率非常低下：您应该跟踪已经找到的质数，并且只能除以这些数。如果已经被2除，为什么要除以4？如果一个数字可被4整除，那么它也可被2整除，因此您早已将其捕获，因此无需将其除以4。您只需要测试被测试数的平方根，因为任何大于该因数的因数都需要乘以一个小于该因数的数，并且在您获得更大的因数时就已经进行了测试。