Python：如何提高函数检查数字是否为素数的效率

Question

对于学校，我需要创建一个函数（不是从模块（即 Sympy）中窃取的）来检查数字是否为素数。但对我来说，挑战是我需要检查相当大的数字。

我写了下面的代码，但我的 VS Code 不断意外崩溃。该功能似乎很慢。 （是的，我知道使用“全局”是不好的做法）

def is_divisible(num, divisor_list):
    for int in divisor_list:
        if num % int == 0:
            return True
    return False

#base prime
primes = [2]

def is_prime(num):
    #to increase efficiency
    global primes

    #getting exceptions out of the way
    if num <= 1:
        return False
    if num == 2:
        return True

    for i in range(3, num + 1, 2):
        if not is_divisible(i, primes):
            primes.append(i)

    return True

非常感谢您的帮助！

Answer 1

在你的代码中有一个嵌套循环，我根本看不出原因。 此外，在第一个循环中，您不需要检查数字本身。

如果您可以使用

math

模块，更好的方法是计算数字的平方根并按以下方式工作：

def is_prime(num):
    if num <= 1:
        return False
    if num == 2:
        return True

    for i in range(3, int(math.sqrt(num)) + 1, 2):
        if num % i == 0:
            return False
        
    return True