是我写此函数来查找质数有效

Question

def is_prime(x):
    '''
    Function to check if a number is prime
    '''
    if x == 2: 
        return True
    if x%2 != 0: #Check if number is even since all primes are odd except 2
        a = [x % i for i in range(2,x+1)] 
        b = [i for i in a if i == 0] # Checks to make sure there's only one modulus of 0
        if len(b) == 1:
            return True
        else:
            return False
    else:
        return False

所以像是的，请问时间复杂度是多少（所有那些0 / n的东西）以及我如何找到它，良好的资源链接会有所帮助（：

Answer 1

当您从2到O(x)运行一个循环时，您的复杂度为x+1。>>

您最多只能检查sqrt(x)。这样会将复杂度降低到O(sqrt(x))。

只需更改此行-

a = [x % i for i in range(2,math.sqrt(x+1))]