python - Python，质数检查器

Question

嗨，我正在制作一个检查数字是否为素数的函数，但它告诉我 9 是素数。

def eprimo(num):
    if num < 2:
        return False
    if num == 2:
        return True
    else:
        for div in range(2,num):
            if num % div == 0:
                return False
            else:
                return True

Answer 1

您的for循环在第一次迭代后立即退出，当它检查您的数字是否可被 2 整除。如果您的数字是偶数，它将返回False; 否则，它将返回True.

解决方法是不要True立即返回；而是等待循环中所有迭代的结束：

for div in range(2, num):
    if num % div == 0:
        return False
return True

或者，使用以下all()构造：

return all(num % div != 0 for div in range(2, num))

Answer 2

无论您是否完成检查，您都将从该 for 循环的第一次迭代中返回。除非数字绝对不是素数，否则您不应该从循环内部返回。删除else并仅True在循环完成时返回。

def eprimo(num):
    if num < 2:
        return False
    if num == 2:
        return True
    else:
        for div in range(2,num):
            if num % div == 0:
                return False
        return True

优化边注：你真的不需要检查所有候选除数到num. 您只需要检查 的平方根num。

Answer 3

您可以提取偶数的测试，然后仅在奇数上循环，而不是测试 range(2,num) 中的所有除数。此外，正如蜥蜴比尔建议的那样，您可以停在 num 的平方根处。这将快两倍：

def eprimo(num):
    if num < 2:
        return False
    if num % 2 == 0:
        return num == 2
    div = 3
    while div * div <= num:
        if num % div == 0:
            return False
        div += 2
    return True