GATE CSE 2003 | Question: 88

Question

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 $\geqslant 3$, and TwoLog_n is initialized to the value of $2^*\lceil \log_2(n) \rceil$

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. $\left\{m \mid m \leq n, (\exists i)\left[m=i!\right]\right\}$

• B. $\left\{m \mid m \leq n, (\exists i) \left[m=i^2\right]\right\}$

• C. $\left\{m \mid m \leq n, \text{m is prime} \right\}$

• D. { }

Comments

In geeksforgeeks ans is given as B.

explaination given as :

// Initialize all values as 0 for (k = 3; k < = n; k++)     A[k] = 0;    for (k = 2; k < = TwoLog_n; k++)     for (j = k + 1; j < = n; j++)         // If k divides j, then A[j] is          // set as 0, else non-zero         A[j] = A[j] || (j % k);    // Print all numbers where A[j] is 0 for (j = 3; j < = n; j++)     if (!A[j])          printf("%d", j);

---

Here the inner loop runs till n. Every inner iteration changes contents of A. For first inner iteration A is 1 for even or 0 for odd places. But now after first inner iteration, second outer iteration comes which starts from k+1, content of A are changed again, previous inner iteration after 1 time become meaningless. So, important thing is matching first outer iteration with first inner iteration ONLY. i think TWOLOGN is just to make confuse us

---

It is whether ceil function or floor function in log2(n) becz in made easy pyq book they have made floor function and here in question ceil function is used ?

Answer 1

The answer is D;

suppose n=4 and TwoLog_n=4;

after executing the code, in place of  { if (!A[j]) printf("%d", j);} if we write { if (A[j]) printf("%d", j);}

then it will print 34 because A[3]=1,a[4]=1; but we are checking for {(!A[j]} from index 3 to 4 so it will print nothing.

Answer 2

as per Geeksofgeeks why answer show me B.

explanation:

[sourcecode language="C"] // Initialize all values as 0 for (k = 3; k < = n; k++) A[k] = 0; for (k = 2; k < = TwoLog_n; k++) for (j = k + 1; j < = n; j++) // If k divides j, then A[j] is // set as 0, else non-zero A[j] = A[j] || (j % k); // Print all numbers where A[j] is 0 for (j = 3; j < = n; j++) if (!A[j]) printf("%d", j); [/sourcecode]

Answer 3

In simple words, it is trying to find ’ i‘ such that i%((i-1)!)=0 for i>=3  it is impossible.

So, it will return an empty set.