The Gateway to Computer Science Excellence
+2 votes
The intended purpose of this code is to precompute all the primes less than N. When it is finished executing, for r ∈ [2, N), bits[r] is supposed to equal 1 if and only if N is composite. Assume that the bits array is initialized to all zeroes.
for ( int x = 2; x < N; x = x + 1 ) {
int y = x
while ( y < N ) {
bits[y] = 1
y = y + x

Which of the following statements is/are true?

I. The algorithm requires O(N) temporary space.

II. The algorithm demonstrates an asymptotic algorithmic complexity of O(N ln(N)).

III. After the initialization shown above, it is possible to determine in O(1) time whether a natural number n < N is prime.

(A) I only

(B) I and II only

(C) II and III only

(D) I, II, and III
in DS by Active (4.9k points) | 222 views

1 Answer

+1 vote

i have implemented this algo(Sieve of Eratosthenes) on Codechef.

but i am conform that I and III are correct.

I==> array is required of size n so we can fill with 0 and 1 for dectacting number is prime or not

III==>.after execution algo we can find in O(1) that number is prime or not.


composite number


Prime number

the complexity is O(nloglogn)

but i am some confused with the code written in question and language of the question.

in question written that ->bits[r] is supposed to equal 1 if and only if N is composite

but bits[2]=1 and 2 is prime not composite.

by Active (2.5k points)
edited by

bits[2] would not be 1 becoz 2 is not composite..bits[2]=0;

and complexity is O(n) possible...see this

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
50,737 questions
57,395 answers
105,446 users