#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