Python素数检查器

Question

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

num=13

while num > a :

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

    print('not prime')

    break

  i += 1

else: # loop not exited via break

  print('prime')

您的算法等效于：

for a in range(a, num):

    if a % num == 0:

        print('not prime')

        break

else: # 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 math

def 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 math

def 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

您的代码存在两个主要问题：

1. 在指定一个非素数之后，即使您已经知道它不是素数，也要继续检查其余除数，这可能导致它在打印“非素数”之后打印“素数”。提示：使用“ break”语句。

2. 在检查所有需要检查的除数之前，请指定一个数字质数，因为您正在循环内打印“质数” 。因此，您会多次获得“素数”，对于每个除数不均等地进入被测数的除数。提示：else仅在循环退出而不会中断的情况下，才在循环中使用子句以显示“素数”。

效率非常低下：

1. 您应该跟踪已经找到的质数，并且只能除以这些数。如果已经被2除，为什么要除以4？如果一个数字可被4整除，那么它也可被2整除，因此您早已将其捕获，因此无需将其除以4。

2. 您只需要测试被测试数的平方根，因为任何大于该因数的因数都需要乘以一个小于该因数的数，并且在您获得更大的因数时就已经进行了测试。