Seongwon implemented the sieve of Eratosthenes in C++ from memory after class. Hyeongseok, sitting next to him, said the code was wrong, and the two decided to count how many times line 6 runs. Given n, compute that count.
The code is as follows.
int n;
cin >> n; // read n
int* sieve = new int[n + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j += i) {
sieve[j] += 1; // line 6
}
}
The outer loop runs i from 1 to n. The inner loop starts j at 1 and adds i while j does not exceed n. Line 6 is the body of the inner loop, and the task is its total execution count.