单选题 适中
#24863

下面代码实现了欧拉(线性)筛,横线处应填写()。 def euler_sieve_for(n): if n < 2: return [] is_composit…

下面代码实现了欧拉(线性)筛,横线处应填写()。

def euler_sieve_for(n):
    if n < 2:
        return []
    is_composite = [False] * (n + 1)
    primes = []

    for i in range(2, n + 1):
        if not is_composite[i]:
            primes.append(i)

        for j in range(len(primes)):  # 填空处
            p = primes[j]
            if i * p > n:
                break
            is_composite[i * p] = True
            if i % p == 0:
                break
    return primes


未登录也能判分,登录后才会记录
答案与解析
正确答案:C
解析
函数目标是生成不超过n的质数列表。使用欧拉筛时,每个合数仅被其最小质因子筛去。外层循环遍历2到n的整数i,内层循环遍历已记录的质数列表primes中的元素p。当i能被p整除时,说明p是i的最小质因子,之后的合数将由更大的i处理,因此立即break。若i为质数,则加入primes。is_composite数组用于标记合数,避免重复筛选。内层循环需遍历当前全部已得质数,故循环范围应为primes的有效索引区间。j作为索引变量,应覆盖0到len(primes)-1的所有值,确保访问每个已知质数p = primes[j]。循环上限为len(primes),下限为0,步长为1,因此range参数应为len(primes)。