线性筛算法中有语句if p * i > n break;，其目的是（）。

es750561 单选题共个子题

def linearSieve(n: int):
    is_prime = [True] * (n + 1)
    primes = []
    for i in range(2, n + 1):
        if is_prime[i]:
            primes.append(i)
        for p in primes:
            if p * i > n:
                break
            is_prime[p * i] = False
            if _____________:
                break
    return primes

降低常数但复杂度仍是 $O(n\log n)$

保证每个合数只被其最小质因子筛到一次，从而 $O(n)$

提高缓存命中率，复杂度仍 $O(n\log\log n)$

不重要，是否 break 都一样

正在加载题目数据…

第空

已答 /

子题

第空

提示

该题型需在试卷/作业中作答，单题练习暂不支持

答案解析

New