AI题库 · GESP-Python五级题库
题目分享 #24864
埃氏筛中将内层循环从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
A
因为2*i 一定不是合数
B
i*i 一定是质数
C
小于i*i 的i 的倍数已被更小质因子筛过
D
这样可以把时间复杂度降为O(n)
AI题库 · 编程考级与信奥赛真题库
查看答案 →
复制链接后可在微信、QQ、小红书等平台粘贴分享;答案与解析在题目页。