My Weblog

Blog about programming and math

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

June 7, 2010 - Posted by | Programming

2 Comments »

  1. 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 | Reply

  2. thanks buddy

    Comment by pawan | June 5, 2011 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: