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

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.

Answer 2

This code implements a variation of the Sieve of Eratosthenes algorithm to find all prime numbers between 3 and n.

---

How it Works

1. First Loop:

   for (k = 3; k <= n; k++) A[k] = 0;

   This loop initializes an array A, marking all numbers from 3 to n as potentially prime (by setting their value to 0).

2. Second Loop (The Sieve):

   for (k = 2; k <= TwoLog_n; k++) ...

   This is the core logic. It iterates from k=2 up to ⌈2∗log2​(n)⌉. For each k, it marks all multiples of k as composite (not prime) by setting their array value to 1. The expression A[j] = A[j] || (j%k) is a clever way of doing this: if j is a multiple of k, j%k is 0 (false), so A[j] remains unchanged. If it's not a multiple, the value doesn't matter for this k. This logic is slightly flawed but aims to sieve out composites. A standard sieve would be if (j%k == 0) A[j] = 1;.

3. Third Loop (Printing):

   for (j = 3; j <= n; j++) if (!A[j]) printf("%d", j);

   This loop goes through the array one last time. If a number j is still marked as 0 (!A[j] is true), it means it was never marked as composite. Therefore, it must be a prime number, and the program prints it.

 

Let's trace the code with n=4.

1. Initialization:

   • n=4

   • TwoLog_n = 2∗⌊log2​(4)⌋=2∗2=4.

   • Array A of size at least 5 (indices 0 through 4).

2. First Loop (sets elements to 0): This loop is irrelevant as array elements are generally initialized to 0 by default, but it would set A[3]=0 and A[4]=0.

   • A is effectively [?, ?, ?, 0, 0, ...].

3. Second Loop (Sieve Logic): This is the main part. It simulates the Sieve of Eratosthenes.

   • The outer loop runs for k from 2 up to TwoLog_n (which is 4).

   • When k = 2:

     • The inner loop runs for j from k+1=3 up to n=4.

     • j=3: A[3] = A[3] || (3 % 2). A[3] is 0. 3%2 is 1 (true). So, A[3] = 0 || 1 becomes 1.

     • j=4: A[4] = A[4] || (4 % 2). A[4] is 0. 4%2 is 0 (false). So, A[4] = 0 || 0 remains 0.

   • When k = 3:

     • The inner loop runs for j from k+1=4 up to n=4.

     • j=4: A[4] = A[4] || (4 % 3). A[4] is 0. 4%3 is 1 (true). So, A[4] = 0 || 1 becomes 1.

   • When k = 4:

     • The inner loop for (j=5; ...) does not run.

   After these loops, the relevant part of array A is A[3]=1, A[4]=1. The code effectively marks composite numbers.

4. Third Loop (Printing):

   • The loop runs for j from 3 to 4.

   • It prints j if !A[j] is true (i.e., if A[j] is 0).

   • j=3: A[3] is 1. !A[3] is false. Nothing is printed.

   • j=4: A[4] is 1. !A[4] is false. Nothing is printed.

Conclusion

For n=4, the program prints nothing. This corresponds to option D) { }.

The code is a variation of the Sieve of Eratosthenes that finds prime numbers. For n=4, there are no prime numbers in the range [3, 4], so the output is the empty set.

Answer 3

for (k = 3;  k <= n; k++) // This assigns 0 to all elements from 3rd element to the nth element
        A[k] = 0; 

for (k = 2; k <= TwoLog_n; k++) // Runs from 2 to 2logn
  for (j = k+1; j <= n; j++)  // runs from k + 1 to n
     A[j] = A[j] || (j%k); // Assigns A[j]=1 if it is already 1 or if j is not divisible by k

what this loop essentially does is it makes A[j] equal to 1 if j is divisible by at least one of 2,3,...,2logn

for k = 2

    j = 3, 4, 5, ..., n | A[4] = 1, A[6] = 1 all even indices become 1

for k = 3

    j = 4, 5, 6, ... , n | A[6] = 1, A[9] = 1, ... all j divisible by 3 becomes 1

This pattern continues until k = 2logn

So for A[j] to be 0, j should be divisible by all of k = 2,3,4,5,....2logn

The lowest value of j = LCM (2,3,4,5,...2logn) >= Product of all primes in (2,3,4,5,...,2logn) > n 

Lowest value of j > n

It is not possible to get a 0 uptil n as the lowest value where we would get A[j] = 0 is when j > n