Python中filter能否逐个输出元素？如何优化素数判断性能？

在素数判断练习中，我发现Python的filter函数并不直接返回列表，必须通过list(filter())才能得到对应的列表对象。我分别用两种方式实现了素数判断逻辑：

初始实现方案 #

1. for循环实现 #

def is_prime_for(n: int):
    if n <= 3:
        return True
    else:
        m = list(range(2, n//2 + 1))     # +1 是为了避免n==4时出现错误结果
    for i in m:
        if n % i == 0:
            return False
    else:
        return True
value = 864203                     
print(is_prime_for(value))

2. filter+lambda实现 #

def is_divisible(num1: float, num2: float):
    if num1 % num2 == 0:
        return True
    else:
        return False

def is_prime(num: int):
    if list(filter(lambda x: is_divisible(num, x), list(range(2, num//2 + 1)))) != []:
        return False
    else:
        return True
value = 864203                 # 从谷歌找到的素数
print(is_prime(value))

性能差异与疑问 #

通过带计时装饰器的测试代码对比发现，filter+lambda实现的函数执行时间是for循环版本的两倍，判断非素数时性能差距更明显。我理解这是因为前者需要遍历整个序列完成过滤后才生成列表，而for循环在找到第一个能整除的数时就直接返回结果。我原本以为判断非素数时，filter会在找到第一个符合条件的元素时就返回结果，而非等全部过滤完成，所以想请教：有没有办法让filter逐个输出过滤后的元素，不用等待整个过滤流程结束？

计时测试代码 #

import time  

def timeis(func):   # 统计函数执行时间的装饰器
    def wrap(*args, **kwargs): 
        start = time.time() 
        result = func(*args, **kwargs) 
        end = time.time() 
        
        print(func.__name__, end - start) 
        return result 
    return wrap 

def is_divisible(num1: float, num2: float):
    if num1 % num2 == 0:
        return True
    else:
        return False
    
@timeis
def is_prime(num: int):
    if list(filter(lambda x: is_divisible(num, x), list(range(2, num//2 + 1)))) != []:  # +1 避免n==4时出错
        return False
    else:
        return True
    
@timeis
def is_prime_for(n : int = 2):
    if n <= 3:
        return True
    else:
        m = list(range(2, n//2 + 1))
    for i in m:
        if n % i == 0:
            return False
    else:
        return True 

value = 864203           # 谷歌找到的素数
# print(is_prime(value))    # 验证该数确实是素数，避免误判
is_prime(value)
is_prime_for(value)

测试输出结果 #

is_prime 0.06304740905761719
is_prime_for 0.02378678321838379

优化后的实现与测试结果 #

经过优化后的代码如下，主要优化点包括：将遍历范围缩小到目标数的平方根（因为若n有大于平方根的因数，则必然存在对应的小于平方根的因数），使用any()/all()替代filter（这两个函数会在满足条件时立即返回，无需生成完整列表）：

import time

def timeis(func):  # 统计函数执行时间的装饰器
    def wrap(*args, **kwargs): 
        start = time.time() 
        result = func(*args, **kwargs) 
        end = time.time() 
        
        print(func.__name__, end - start) 
        return result 
    return wrap 

def is_divisible(num1: float, num2: float):
    if num1 % num2 == 0:
        return True
    else:
        return False

@timeis
def is_prime(num: int):
    if any(is_divisible(num, x) for x in range(2, int(num**0.5 + 1.01))):   # 参考Trincot的回答与OneCricketeer的评论优化了数学逻辑
        return False
    else:
        return True

@timeis
def is_prime_all(num: int):                           # Trincot提供的实现
    return all(num % x for x in range(2, int(num**0.5 + 1.01)))

@timeis
def is_prime_all_mod(num: int):                       # Trincot实现的修改版，判断非素数时更快
    return all(num % x for x in range(2, num//2 + 1))

@timeis
def is_prime_for(n : int = 2):       # 参考Trincot的回答优化了数学逻辑
    if n <= 3:
        return True
    else:
        m = range(2, int(n**0.5 + 1.01))
    for i in m:
        if n % i == 0:
            return False
    else:
        return True 

@timeis
def is_prime_while(n : int = 2):    # 参考Trincot的回答优化了数学逻辑
    if n <= 3:
        return True
    else:
        x = int(n**0.5 + 1.01)
        i = 2
        while i < x:
            if n % i == 0:
                return False
            i += 1
        else:
            return True 

# value = 28122221                 # 谷歌找到的素数
value = 28122222                # 用于测试的非素数
# print(is_prime(value))  
is_prime(value)
is_prime_all(value)
is_prime_all_mod(value)
is_prime_for(value)
is_prime_while(value)

素数测试输出 #

is_prime 0.00029087066650390625
is_prime_all 0.0001399517059326172
is_prime_all_mod 0.607919454574585
is_prime_for 0.0001266002655029297
is_prime_while 0.00017380714416503906

非素数测试输出 #

is_prime 1.0013580322265625e-05
is_prime_all 7.152557373046875e-06
is_prime_all_mod 1.6689300537109375e-06
is_prime_for 1.1920928955078125e-06
is_prime_while 4.76837158203125e-07

内容的提问来源于stack exchange，提问作者bola8divad