I am new to this forum and do not know the protocols of this forum very well, so forgive me for my ignorance. My question is related to the spoj problem https://www.spoj.pl/problems/KPRIMES2/ . I get TIME LIMIT EXCEED for this problem. I think the bottleneck of this program generates 10 ^ 9. Can anyone suggest how to improve this sieve, a faster way to generate a simple one or how to solve this problem. Here is a sketch of my algorithm
This program generates all primes of the form 2k + 1 and encodes these primes into 32-bit integers of the array a [i], in which unset bit represents primes.a [0] encodes 3,5,7 ...... .65.a [1] encodes 67 and so on. I took the auxiliary array bitcnt [], in which bitcnt [i] stores the sum of the canceled bits [0], a [1], ......... a [i]. I used bitcnt for binary search and found the position of the kth number. Here is a little explanation of the functions. The prime () function generated primes, and I encoded the primes onto the bits of the number [32-bit unsigned integer]. bit-bit stores the sum of the unsaved bits of array a for binary search purposes. bsearchupper (int m) returns the bitcnt index in which m lies. Finally, in the main function, I save how many primes are up to the upper bound of m and started decreasing the value until I got K. Thank you.
Edit: statement of a problem from SPOJ
Enter
An integer indicating the number of Q queries (equal to 100,000) and Q strings, each of which contains a single integer K between 1 and 50,000,000 inclusive.
Exit
Q lines with the answer of each request: Kth prime.
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; }