python - 为什么我的素数测试仪中的模数条件不起作用？

Question

我正在尝试（但失败）编写一个简单的函数来检查一个数字是否为素数。我遇到的问题是，当我到达 if 语句时，无论输入如何，它似乎都在做同样的事情。这是我的代码：

def is_prime(x):
    if x >= 2:
        for i in range(2,x):
            if x % i != 0:    #if x / i remainder is anything other than 0
                print "1"
                break
            else:
                print "ok"
        else:
            print "2"
    else: print "3"

is_prime(13)

带有评论的那一行是我确定问题所在。无论我使用什么整数作为参数，它都会打印“1”。我很抱歉这可能是一个愚蠢的问题，我根本不是一个有经验的程序员。

Answer 1

您的代码实际上非常接近功能。您的条件中只是有一个逻辑错误。

您可以对素数测试进行一些优化，例如只检查给定数字的平方根。

def is_prime(x):
    if x >= 2:
        for i in range(2,x):
            if x % i == 0: # <----- You need to be checking if it IS evenly
                print "not prime" # divisible and break if so since it means
                break             # the number cannot be prime
            else:
                print "ok"
        else:
            print "prime"
    else:
        print "not prime"

Answer 2

问题是这一行：

if x % i != 0: 

您正在测试 if x % iis not 0，这对于任何一对相对质数的整数都是正确的（因此，您总是将其打印出来）

它应该是：

if x % i == 0:

Answer 3

尝试使用 return 语句代替（或附加于）打印语句，例如：

from math import sqrt # for a smaller range

def is_prime(x):
    if x <= 2:
        return True
    for i in range(2, int(sqrt(x)) + 1):
        if x % i == 0:
            print "%d is divisible by %d" % (x,i)
            return False
    return True    

is_prime(13)
True

is_prime(14)
14 is divisible by 2
False

Answer 4

这种检查可以是单个表达式：

def is_prime(n):
    return n>1 and all(n%k for k in range(2,n//2))