python - python中的原始性测试

This question already has answers here:

How to create the most compact mapping n → isprime(n) up to a limit N?

(32个答案)


5年前关闭。




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

根据Wikipedia，primality test如下:



我首先排除了偶数(除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。

最佳答案

简而言之，您的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语句。