In the following program fragment, j, k, n, and TwoLog_n are integer variables, and A is an array of integers. The varia...

Question

In the following 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 >= 2, and TwoLog_n is initialized to the value of 2*floor(log_2(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] || (!(A[k]) && !(A[j/k]));

The set of numbers printed by this program fragment is

A. {m | m <= n_0(3) m = i!}
B. {m | m <= n_0(3) m = i^2}
C. {m | m <= n, m is prime}
D. {}

Accepted Answer

The program identifies (marks with A[j]=1) all composite numbers; the numbers remaining unmarked (A[j]=0) are exactly the primes <= n. Answer: C. The program initializes all A[k] for k>=3 to 0, then uses a nested loop to set A[j]=1 if A[j] is already 1 OR if both A[k]=0 and A[j/k]=0. Since A[2]=0 and all A[k] start as 0, the condition !A[k] && !A[j/k] is true when neither k nor j/k has been marked composite. The logic identifies composite numbers — numbers that can be expressed as k*(j/k). The indices j where A[j] remains 0 are the primes.