#3378. [GESP202403 五级 C++] 第 10 题

[GESP202403 五级 C++] 第 10 题

在埃拉托斯特尼筛法中,要筛选出不大于 n 的所有素数,最外层循环应该遍历什么范围( )?

vector<int> sieveOfEratosthenes(int n) {
    std::vector<bool> isPrime(n + 1, true);
    std::vector<int> primes;
    _______________________ {
        if (isPrime[i]) {
            primes.push_back(i);
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    for (int i = sqrt(n) + 1; i <= n; ++i) {
        if (isPrime[i]) {
            primes.push_back(i);
        }
    }
    return primes;
}

{{ select(1) }}

  • for (int i = 2; i <= n; ++i)
  • for (int i = 1; i < n; ++i)
  • for (int i = 2; i <= sqrt(n); ++i)
  • for (int i = 1; i <= sqrt(n); ++i)