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

def is_prime(n):
    return all(n%j for j in xrange(2, int(n**0.5)+1)) and n>1

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

Answer 3

一旦你知道一个数字不是素数，你就需要停止迭代。找到素数后添加一个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和其他：

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