Codewars Gap in primes素数间隔题大输入超时优化咨询

原代码核心问题 #

• 埃氏筛实现未利用素数奇偶性特征，存在大量无效计算
• 筛选完成后额外生成全量素数列表，既占用内存又增加遍历开销
• 未做前置剪枝逻辑，对特殊输入场景可直接返回结果，无需执行筛选
• 存在边界逻辑错误：过滤条件写的i>m，不符合题目要求的包含m的规则

具体优化方向 #

1. 前置剪枝 #

除2以外所有素数都是奇数，两个奇数的差必然为偶数：

• 若间隔g为奇数，唯一可能的素数对是[2, 3]，直接判断区间是否包含这两个数即可返回结果，无需后续计算

2. 优化埃氏筛实现 #

• 初始化筛数组时直接把所有偶数位置标记为非素数，仅需要处理奇数位
• 筛除循环从3开始，步长设为2，仅遍历奇数，筛除的倍数也仅处理奇数区间，计算量直接减少一半
• 用Python原生切片赋值替代for循环做标记，切片操作为底层C实现，执行效率远高于纯Python循环

3. 优化结果遍历逻辑 #

• 无需生成全量素数列表，直接从m开始遍历筛数组，记录上一个遇到的素数，每遇到新的素数就计算和上一个素数的差值
• 差值等于g时直接返回结果，不需要遍历完整个区间，提前终止

优化后代码示例 #

def gap(g, m, n):
    # 前置剪枝：奇数间隔只有[2,3]符合
    if g % 2 == 1:
        if m <= 2 and n >= 3:
            return [2, 3]
        return None
    
    if n < 2:
        return None
    sieve = [True] * (n + 1)
    sieve[0] = sieve[1] = False
    # 偶数直接标记为非素数
    for i in range(4, n+1, 2):
        sieve[i] = False
    # 筛除奇数的倍数
    p = 3
    while p * p <= n:
        if sieve[p]:
            # 跳过偶数倍数，步长设为2*p
            sieve[p*p : n+1 : 2*p] = [False] * len(sieve[p*p : n+1 : 2*p])
        p += 2
    
    # 边遍历边找符合条件的素数对
    prev_prime = None
    for num in range(max(m, 2), n+1):
        if sieve[num]:
            if prev_prime is not None and num - prev_prime == g:
                return [prev_prime, num]
            prev_prime = num
    return None

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