#3525. [GESP202509 五级 C++] 第 7 题

[GESP202509 五级 C++] 第 7 题

函数 linearSieve 实现线性筛法(欧拉筛),横线处应填入( )。

vector<int> linearSieve(int n) {
    vector<bool> is_prime(n+1, true);
    vector<int> primes;
    for(int i = 2; i <= n; i++) {
        if(is_prime[i]) primes.push_back(i);
        for(int p : primes) {
            if(p * i > n) break;
            is_prime[p * i] = false;
            if(________) break;
        }
    }
    return primes;
}

{{ select(1) }}

  • i % p == 0
  • p % i == 0
  • i == p
  • i * p == n