单选题
适中
#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)。