SPOJ Problem KPRIMES2

Question

I am new to this forum and not well aware of protocols of this forum so pardon me for my ignorance. My question is related to spoj problem https://www.spoj.pl/problems/KPRIMES2/. I am getting TIME LIMIT EXCEED for this problem.I think the bottleneck of this program is generating 10^9.Could some one suggest how to improve this sieve , faster way to generate prime or how to solve this problem. Here is sketch of my algorithm

This program generates all the primes of form 2k+1 and encoded these primes into 32 bit integers of array a[i] in which unset bit represents primes.a[0] encodes 3,5,7.......65.a[1] encodes 67 onwards and so on. I have taken a auxiliary array bitcnt[] , in which bitcnt[i] stores sum of unset bits of a[0], a[1],.........a[i]. I used bitcnt for binary search and find the position of kth number.Here is bit explanation of functions. prime() function generated primes and i encoded the primes onto bits of number[32 bit unsigned integer]. bitcnt array stores sum of unset bits of array a for binary search purpose. bsearchupper(int m) return index of bitcnt in which m lie. Finally in main function , i am storing how many primes are upto upperbound of m and started decreasing value till i got K. Thank you.

Edit:Problem statement from SPOJ

Input

An integer stating the number of queries Q(equal to 100000), and Q lines follow, each containing one integer K between 1 and 50000000 inclusive.

Output

Q lines with the answer of each query: the Kth prime number.

Example

Input: 8 1 10 100 1000 10000 100000 1000000 10000000

Output: 2 29 541 7919 104729 1299709 15485863 179424673

#include<cstdio>
#include<vector>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<ctime>
#define Lim 1000000000
using namespace std;
unsigned int a[(Lim>>6)+10],bitcnt[(Lim>>6)+10];
int bound;
void prime()
{

    int p_1,q_1,p_2,q_2,Ub=sqrt(Lim*1.0);
    for(int i=3;i<=Ub;i+=2)
    {
            p_1=(i-3)>>6,q_1=((i-3)>>1)&31; 
            if(!(a[p_1] & (1L<<q_1))) 
            for(int j=i*i;j<Lim;j+=i) 
               if(j&1) 
                {
                p_2=(j-3)>>6,q_2=((j-3)>>1)&31;
                a[p_2]|=(1L<<q_2);
                }
    }

    int cnt=0;bound=0;
    for(int i=0; i<=((Lim>>6)-1);i++) 
     {
        //p_1=(i-3)>>6,q_1=((i-3)>>1)&31;
        cnt+=__builtin_popcount(~a[i]);
        bitcnt[bound++]=cnt;
        //cout<<bound-1<<"---"<<bitcnt[bound-1]<<endl;
    }
    //cout<<cnt<<endl;
}
    int bsearchupper(int m)
{
    int lo=0,hi=bound,mid;
    while(lo<hi)
    {
        mid=lo+((hi-lo)>>1);
        if(bitcnt[mid]<=m)lo=mid+1;
        else hi=mid;

    }
    //cout<<"lo= "<<lo<<" mid= "<<mid<<" hi= "<<hi<<endl;
    return lo;
}
    int main()
{
    //clock_t start,end;
    //start=clock();
    prime();
    int t,k,c,ret,w;
    for(scanf("%d",&t);t>0;t--) 
    {
        scanf("%d",&k);
        if(k==1) {cout<<"2"<<endl;continue;}
        k=k-2;
        c=bsearchupper(k);
        ret=bitcnt[c],w=32*(c+1);
        for(int i=31;i>=0;i--)
        {

            if(!(a[c] & (1L<<i))) 
             {
                ret--;
                if(ret==k) printf("%d\n",3+(w-1)*2);

             }
            w--;
        }   
    }

    //end=clock();
            //cout<<((end-start)/(double)CLOCKS_PER_SEC)<<endl; 
}

Answer 1

Consider compacting your prime storage even more. For example, in every block of 2*3*5*7*11=2310, there are exactly 1*2*4*6*10=480 numbers that have no prime factor of 11 or less, which you can pack into 15 array entries rather than (about) 36. That will eliminate a few hundred million bit operations sieving out those small factors. You'll have to change your indexing into the bit array; a couple of constant arrays of length 2310 giving the bit index (if it exists) and array element offset would help here, and a similar array (of length 480) converting bit positions back into values mod 2310.