素数检查行为很奇怪

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 时给出的结果是：

 not prime
not prime
not prime
prime

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

原文由 Chris 发布，翻译遵循 CC BY-SA 4.0 许可协议

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')

如果将它放入函数中，则可以免除 break 和 for-else：

 def is_prime(n):
    for i in range(3, n):
        if n % i == 0:
            return False
    return True

即使您要像这样对质数进行暴力破解，您也只需要迭代到 n 的平方根。此外，您可以跳过测试两个之后的偶数。

有了这些建议：

 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))

原文由 Steven Rumbalski 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

def isprime(n):
    '''check if integer n is a prime'''

    # make sure n is a positive integer
    n = abs(int(n))

    # 0 and 1 are not primes
    if n < 2:
        return False

    # 2 is the only even prime number
    if n == 2:
        return True

    # all other even numbers are not primes
    if not n & 1:
        return False

    # range starts with 3 and only needs to go up
    # the square root of n for all odd numbers
    for x in range(3, int(n**0.5) + 1, 2):
        if n % x == 0:
            return False

    return True

取自：

http://www.daniweb.com/software-development/python/code/216880/check-if-a-number-is-a-prime-number-python

原文由 Destructor 发布，翻译遵循 CC BY-SA 3.0 许可协议