Programming

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 ≥ 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);

Can someone go step by step and say me what is happening here?

[All a[j] will get !=0 value here,rt?]

Plz explain

Comments

"TwoLog_n is initialized to the value of" ?

---

chk plz

Answer 1

A[j] = 0, if j % k == 0, for j >= 3 && j <= N and k >= 2 and k <= $2*\log_2N$.

Else A[j] = 1. Once some A[j] becomes 1 it will remain that way through out the execution.

This means that it checks for all j in the range 3 to N, wether that j is divisible by all k from 2 to $2*\log_2N$.

For indices satisfying above criteria, A[j] will be 0 an for the rest it will be 1.

The printing loop at the end will print those indices where A is 0.

 

Finally the loop will not print anything. Check comments below.

Comments

As I mentioned in my answer, the nested for loops are checking if numbers in the range 3 to N are divisible by all numbers in the range 2 to $2*\log_2N$. If this is true, A[i] will be 0 else it will be 1. For any two numbers i and j, there are two possibilities. Either i % j == 0 or i % j == k, where k != 0. These two can be considered the two holes in the pigeon hole principle.

Now the loop starts checking from 3 to N (for int j = k+1; j <= N; ++j). The minimum possible value of TwoLogN is 4 for N = 3. Thus each number j is checked for divisibility by atleast 4 numbers. So there will be atleast one number which doesnt divide j. Thus each A[j] will be 1. The printing loop tries to print indices such that A[j] == 0. (!A[j] is true when A[j] == 0)

EDIT: For N = 3, TwoLogN = 2. So 3 is checked for divisibility for only 2. But 3%2 = 1. So A[3] = 1. Rest all numbers are checked by atleast 2 numbers. So there will be atleast 1 non divisor and all A[j] = 1.

---

But pegion hole principal is more than one pegion in atleast one hole.

---

@Srestha Yes you are correct. This is not pigeon hole principle. But the idea is similar.

Consider 3 numbers X, Y and Z. Y and Z are consecutive numbers according to the conditions in the code. We will check if X is divisible by Y and Z. Each number is either divisible by a number or it's not. 2 or more consecutive numbers can not be in just 1 bin. (which means for 2 consecutive numbers Y and Z and some number X >= Y and X >= Z. Both X%Y == 0 && X%Z == 0 can not be true.) They will need atleast 2 bins. So there will be atleast 1 number which doesnt divide X.

Answer 2

Say n=6

Now, in at last loop we are printing j=3 to 6

which all are non zero.

We will print those j which are !A[j]=1

means A[j]=0

But in j=3 to 6 there is no such value.

So, print nothing

Comments

@air1,@vijay chk this