The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+28 votes

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. { }

asked in Algorithms by Veteran (59.7k points)
edited by | 2.3k views
Couldn't understand. Someone plz explain clearly.

4 Answers

+22 votes
Best answer

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. 

answered by Veteran (367k points)
edited by

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??


@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)

If the second condition was realized, it would print co-primes less than n. Am i right ?
@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.
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?

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

@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.


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

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

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

answered by Boss (23.1k points)
nice answer!!.
+7 votes
Answer: D

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

answered by Boss (34k points)
Yes. I have updated the answer :)
+3 votes

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.

answered by Active (2.4k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,147 questions
49,639 answers
65,807 users