2.5k views

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

1. $\left\{m \mid m \leq n, (\exists i)\left[m=i!\right]\right\}$

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

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

4. { }

edited | 2.5k views
0
Couldn't understand. Someone plz explain clearly.

The nested loop is taking all integers from $2$ to $2\ast \log_2 n$. Take all their non-multiples before $n$, and make the corresponding entry in $A$ as $1$. For example, for $2$, and $n = 10, A[3], A[5], A[7]$, and $A[9]$are made $1$. Similarly for $3$, $4$, ... till $2\ast \log n$. So, if any entry $A[p]$ is $1$ means it must be a multiple of $2, 3, .... 2\ast \log_2 n$, which is $\left ( 2 \log n \right )!$ and is greater than $n$. So, for no index $p$, $A[p]$ will be $0$. So, answer is D

Suppose the line

A[j] = A[j] || (j%k);

is replaced with

A[j] = A[j] || !(j%k);

Now, the nested loop is taking all integers from $2$ to $\log_2 n$, take all their multiples before $n$, and make the corresponding entry in $A$ as $1$. For example, for $2$, and $n = 10, A[4], A[6], A[8]$ and $A[10]$ are made $1$. Similarly for $3, 4, ...$ till $2\ast \log n$ . So, for all non-prime indices of $A$, we will have a $1$, and for prime indices we have a $0$. And we print $i$ if $A[j]$ is $0$ meaning $j$ is prime.

edited
0

what is the meaning of  "| |" here ?

A[j] = A[j] || (j%k);

2nd query..

for   A[j] = A[j] || (j%k);

all elements of A[p] is 1 because all elements are indivisible by any one element out of ( 2 to 2*log n elements).

am i right here??

+5

@arjun ,  its a typo here So, if any entry A[p] must be 1 means it must be a multiple of 2, 3, .... 2log2 n,  (1 instead of 0)

0
If the second condition was realized, it would print co-primes less than n. Am i right ?
0
@Khush+tak || in C is for logical OR. That is it takes two operands, and returns 1 if any one of them is true. And in C, any non-zero value is treated as TRUE.

For second, your statement is correct. Just replace "any one" by "at least one" or "some".

@ryan It prints primes less than n.
0
for (k = 2; k <= TwoLog_n; k++)
for (j = k+1; j <= n; j++)
A[j] = A[j] || (j%k);

it is printing all values <n ,right?

0
it makes ann A[j] values as 1. But we print only when !A[j] = 1 => when A[j] = 0.
+1

@Arjun, @Rajesh Pradhan, @Pankaj kumar and @Rajarshi Sarkar,

Does LCM of (2,3,.......2*lon(n)) is always greater than n ?

Because if answer is no then it seens program will print multiple of LCM less than n.

0

implementation of this program if (j%k) is replaced by !(j%k)

https://ideone.com/q0exTM

0
this is a well known algorithm named "Sieve of Eratosthenes", after Eratosthenes of Cyrene, a Greek mathematician.

take n=3 So TwoLog_n=4 . Suppose A[4]

0

The code sets 1 at all array index after A[2].

Ref: http://ideone.com/2bsRHY
+1
Yes. I have updated the answer :)

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.

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]

1
2