faster than binary search

general
, , ,
1

i have a list of prime no. with its rank as its value in a map .
like map<int ,int > mymap ;
mymap[2]=0
mymap[3]=1
mymap[5]=2

and i am trying to calculate the position of nth prime no in the list by this way as
position=mymap[required no]

but it seems it is not fast enough
plz help me in a right directiion…???

2

Hello @vivek07672,

You can start by generating all the primes using a common algorithm, like the Sieve of Erathostenes… This algorithm allows you to generate all the prime numbers up to N, in a reasonable fast time, which is usually enough for the requested limits when working with prime numbers.

Once you have all the prime numbers in a container that supports iteration (like a vector or an array), using a well implemented binary search is more than enough to find what you want.

Also, I understand that this question can be related to the problem CHEFHACK and that the contest is still running but since you haven’t asked for any test cases specifications and as it seems you have thought about the problem a bit, I decided to answer and hopefully help you, but please keep in mind that live contest questions must be asked in a way that doesn’t give too much away regarding a particular problem, just like you did. :slight_smile:

Best regards,

Bruno

3

Hi! To answer your question, you could just tweak the sieve of Eratosthenes to get your answer.
Wikipedia lists the algorithm as:

Input: an integer n > 1
 
Let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.
 
for i = 2, 3, 4, ..., √n :
  if A[i] is true:
    for j = i^2, i^2+i, i^2+2i, ..., n:
      A[j] := false
 
Now all i such that A[i] is true are prime.

You can modify it in this way:

Input: an integer n > 1

Let A be an array of Integer values, indexed by integers 2 to n,
initially all set to 0.

Let count be an integer set to 1 initially
 
for i = 2, 3, 4, ..., √n :
  if A[i] = 0:
    A[i] := count
    count := count + 1
    for j = i^2, i^2+i, i^2+2i, ..., n:
      A[j] := -1
for i < n :
  if A[i] = 0
    A[i] := count
    count := count + 1

Now all i such that A[i] > 0 are prime and A[i] denotes the index of this prime in the list of primes till n.

Hope this helps :slight_smile:

4

Vivek, Vivek.
You can’t ask for help for problems during live contest.
It is obvious that you have issue with the problem CHEFHACK.

And you guys why are you helping him?

OK. I have deleted this question until the end of the contest.

1 Like
5

Correction. can -> can’t

6

O-o-ops… Fixed. It is so easy to miss this crappy 't :slight_smile: