Embercode: AI-powered software engineer course

1. What does this program print? ``

cpp
#include <iostream>
#include <vector>
using namespace std;

int main() {
    const int n = 10;
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    long long writes = 0;
    for (int p = 2; p * p <= n; ++p) {
        if (!is_prime[p]) continue;
        for (int m = p * p; m <= n; m += p) {
            is_prime[m] = false;
            ++writes;
        }
    }
    cout << "writes: " << writes << '\n';
}

``

writes: 5writes: 4writes: 9writes: 13

2. What does this program print? ``

cpp
#include <iostream>
#include <vector>
using namespace std;

int count_primes_below(int n) {
    if (n <= 2) return 0;
    vector<bool> is_prime(n, true);
    is_prime[0] = false;
    is_prime[1] = false;
    for (int p = 2; p * p < n; ++p) {
        if (!is_prime[p]) continue;
        for (int m = p * p; m < n; m += p) is_prime[m] = false;
    }
    int count = 0;
    for (int i = 0; i < n; ++i) {
        if (is_prime[i]) ++count;
    }
    return count;
}

int main() {
    cout << count_primes_below(20) << '\n';
}

``

79810

3. The Sieve of Eratosthenes, run for a limit n, does about how much work? The lesson counts its writes and gives the growth class for them.

O(n^2)O(n log log n)O(2^n)O(log n)

4. Trial division checks one number m by trying each d from 2 up to m - 1. For a prime m, how many divisor checks does it make?

log2(m)1m - 2m + 1

5. In for (int p = 2; p * p <= n; ++p), the loop stops once p times p is larger than ___.

Type your answer.