In the following C program fragment, j, k n and TwoLog_n are integer…
2003
In the following C program fragment, j, k n and TwoLog_n are integer variables, and A is an array of integers. The variable n is initialized to an integer ≥ 3, and TwoLog_n is initialized to the value of 2*⌈log2(n)⌉
for (k = 3; k < = n; k++)
A[k] = 0;
for (k = 2; k < = TwoLog_n; k++)
for (j = k + 1; j < = n; j++)
A[j] = A[j] || (j % k);
for (j = 3; j < = n; j++)
if (!A[j]) printf("%d", j);
The set of numbers printed by this program fragment is
- A.
{m | m ≤ n, (∃ i) [m = i!]} Here i! mean factorial of i
- B.
{m | m ≤ n, (∃ i) [m = i2]}
- C.
{m | m ≤ n, m is prime}
- D.
Last print never executes
Attempted by 51 students.
Show answer & explanation
Correct answer: D
Answer: The final print never executes (no numbers are printed).
Reasoning:
The array entries A[3..n] are initialized to 0.
Each time the inner assignment runs, A[j] becomes A[j] || (j % k). Thus A[j] remains 0 after all loops only if for every k that updates index j we have j % k == 0.
Let t = TwoLog_n = 2 * ceil(log2(n)). For a given j (3 ≤ j ≤ n) the relevant k values are 2 ≤ k ≤ min(t, j-1). If A[j] stayed zero then j would be divisible by every integer from 2 up to that minimum.
That is impossible: if the minimum is j-1 then no j ≥ 4 can be divisible by all integers 2..j-1; if the minimum is t then j would have to be at least lcm(2..t), but lcm(2..t) grows faster than n when t = 2 * ceil(log2(n)), so no j ≤ n can equal such an lcm. Therefore no j can satisfy the condition to keep A[j] == 0.
Consequently, every A[j] for j = 3..n is set to a nonzero value by some iteration, and the final if (!A[j]) printf(...) never succeeds for any j.