## SPOJ TDKPRIME

The problem is to find kth prime. The naive sieve will time out but a simple observation that except 2 all primes are odd lead to solution.(Although my solution is not fastest but accepted using this idea) . Implementation of my idea.

#include<cstdio> #include<iostream> #include<vector> using namespace std; #define Lim 86029000 vector<bool> b((Lim>>1)+100); int p[5000100]; void prime() { for(int i=3;i<=9257;i+=2) if(!b[(i-3)>>1]) for(int j=i*i;j<Lim;j+=i) if(j&1) b[(j-3)>>1]=1; p[0]=2; int cnt=1; for(int i=0;2*i<Lim;i++) if(!b[i]) p[cnt++]=2*i+3; /*for(int i=0;i<10;i++) cout<<p[i]<<" "; cout<<endl; for(int i=cnt-10;i<cnt;i++) cout<<p[i]<<" "; cout<<cnt<<endl;*/ } int main() { prime(); int k,q; for(scanf("%d",&q);q>0;q--) scanf("%d",&k) , printf("%d\n",p[k-1]); }

Advertisements

could u plz xplain how does right shift of i-3 and j-3 is working??

and how prime wub b of form 2*i+3 always??

Comment by Shubham Gupta | June 2, 2011 |

thanks buddy

Comment by pawan | June 5, 2011 |