#14028. [GESP202609 五级 C++] 第 6 题
[GESP202609 五级 C++] 第 6 题
下面代码实现线性筛法。为了保证每个合数只被其最小质因子筛去一次,横线处应填写( )。
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;
}
{{ select(1) }}
- p % i == 0
- i % p == 0
- i == p
- i * p == n