线性筛算法中有语句 if p * i > n break;,其目的是( )。
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 都一样