单选题
适中
#24864
埃氏筛中将内层循环从j = i*i 开始而不是j = 2*i 的主要原因是()。 def eratosthenes_sieve_for(n): if n < 2…
埃氏筛中将内层循环从j = i*i 开始而不是j = 2*i 的主要原因是()。
def eratosthenes_sieve_for(n): if n < 2: return [] is_composite = [False] * (n + 1) primes = [] for i in range(2, n + 1): if is_composite[i]: continue primes.append(i) # 用for循环模拟C++的 j = i*i; j <=n; j +=i for j in range(i * i, n + 1, i): is_composite[j] = True return primes
答案与解析
正确答案:C
解析
埃氏筛法标记合数时,对于当前质数i,其倍数中需被筛去的合数从i*i开始。因小于i*i的i的倍数可表示为k*i(k < i),其中k必有小于i的质因子,这些倍数已在处理更小质数时被标记。内层循环跳过2*i、3*i等直至i*i,是因它们已被先前步骤覆盖。时间复杂度仍为O(n log log n),未降至O(n)。i*i不一定是质数,且2*i在i>1时为合数。