Euclid and sieves

Questions 1 to 5 of 8

1. 1. An AI tool wrote a linear sieve. It changed the inner loop's stop test from if (p > lp[i] || p * i > n) break; to if (p * i > n) break; and changed nothing else. The program still prints 78498 for the number of primes up to 10^6. What is the problem?

   The counts are wrong for every n above 10, so the sample failsThe counts stay right, but some composites are written more than once, so the run loses its linear time boundThe program crashes with an array index out of range when n is 10^6The sieve now finds only the primes up to the square root of n
2. 2. How many primes are there up to 10^6? Give the count.

   Type a number.

3. 3. The odd-only sieve sets its upper index with half = n / 2 instead of (n - 1) / 2. Which statements about this bug are true?

   Pick every answer that is true.

   For n = 4 it reports 3 primes instead of 2The bug only shows up when n is oddIn the odd-only array, the index of 97 is 48The bound n / 2 is correct for every n, because the extra odd number is always prime
4. 4. In C++, what does -7 % 3 evaluate to? Give the number.

   Type your answer.

5. 5. Put the first three steps of Euclid's algorithm for gcd(1071, 462) in the order they run.

   Use the arrows to put the steps in order.

   1. 1.462 mod 147 = 21↑↓
   2. 2.1071 mod 462 = 147↑↓
   3. 3.147 mod 21 = 0↑↓