下列线性筛的代码片段中,当枚举到质数 p 且 i % p == 0 时,使用 break; 语句停止继续枚举。这样做的主要目的是( )。
for (int i = 2; i <= n; ++i) {
if (!is_composite[i])
primes.push_back(i);
for (int p : primes) {
if (i * p > n)
break;
is_composite[i * p] = true;
if (i % p == 0)
break; // 这条语句的目的是?
}
}
- A. 保证递归深度不超过 O(log n)
- B. 保证每个合数只被它的最小质因子筛去一次
- C. 保证每个素数都被标记为合数
- D. 把筛法时间复杂度提高到 O(n log n)
正确答案：B