我写这个函数是为了找到有效的素数吗

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

1. 您只需要测试奇数，但2除外，您可以在循环之前专门测试它。这不会改变复杂性，因为它是一个常数，但它将时间减少了一半
2. 您应该只测试math.sqrt(x)以下的数字。这将最坏情况复杂性从O（n）更改为O（sqrt（n））
3. 您应该在找到因子后立即停止，而不是创建所有x % i的列表。这提高了最佳案例的复杂性

import math

def is_prime(x):
    '''
    Function to check if a number is prime
    '''
    if x == 2: 
        return True
    if x % 2 == 0:
        return False
    for i in range(3, int(math.sqrt(x))+1, 2):
        if x % i == 0:
            return False
    return True

比检查所有奇数更好的是使用Sieve of Eratosthenes只检查素数