下面代码实现线性筛法。为了保证每个合数只被其最小质因子筛去一次,横线处应填写( )。
vector<int> linearSieve(int n) {
vector<bool> composite(n + 1, false);
vector<int> primes;
for (int i = 2; i <= n; i++) {
if (!composite[i])
primes.push_back(i);
for (int p : primes) {
if ((long long)i * p > n)
break;
composite[i * p] = true;
if (__________________)
break;
}
}
return primes;
}
- A.
p % i == 0 - B.
i % p == 0 - C.
i == p - D.
i * p == n