python中的原始性测试[重复]

Question

这个问题已经在这里有了答案 ：

如何创建最紧凑的映射n→isprime（n）直到极限N？ （31个答案）

5年前关闭。

我正在尝试在Python中做一个简单的素数测试。

根据Wikipedia的原始性测试如下：

给定输入数n，检查2到n − 1之间的整数m是否除以n。如果n可被任何m整除，则n为合成，否则为质数。

我首先排除了偶数（除2外）作为素数的候选项

def prime_candidates(x):
    odd = range(1, x, 2)
    odd.insert(0, 2)
    odd.remove(1)
    return odd

然后根据上述规则编写一个函数以检查素数。

def isprime(x):
    for i in range(2, x-1):
            if x % i == 0:
                    return False
            else:
                    return True

这是主要功能，它遍历8000个主要候选人的名单并测试其首要性

def main():
    end = 8000
    candidates = prime_candidates(end)
    for i in candidates:
            if isprime(i) and i < end:
                    print 'prime found ' + str(i)

问题在于，isprime对于不是素数的数字，该函数返回True。

Answer 1

简而言之，您将isprime(x)检查数字是否为奇数，然后在之后退出if x % 2 == 0。

尝试进行一些小的更改，以便您实际上可以迭代：

def isprime(x):
    for i in range(2, x-1):
        if x % i == 0:
            return False
    else:
        return True

请注意，这else:现在是for循环的一部分，而不是if语句。