## Problem Link

http://www.spoj.com/problems/TDKPRIME/

## Problem Description

In this problem, We need to print the value of kth prime(max value of k is 5000000) for a number of test cases.

## Concepts Used

This problem is based on prime sieve(Sieve of Eratosthenes).

## Code

```
#include<stdio.h>
#include<vector>
/*To check whether a number i is prime or not,we need to check a[i/2] or a[i>>1] whether it is true or false*/
#define isprime(i) (a[i>>1])
/*number is non prime if correpsonding entry is false*/
#define nonprime(i) (a[i>>1]=false)
/*boolean vector used for marking*/
std::vector<bool>a(100000002,true);
/*array used for storing prime numbers*/
static long long int arr[8000000];
int n=100000000;
int i,j,l;
void sieve()
{
for(i=3;i<=10000;i+=2)
{
/*we do not need to mark multiples of already marked numbers*/
while(!isprime(i))
{
i+=2;
}
j=i*(i-2);
/*l=(2*i)-implemented using left shift*/
l=i<<1;
while((j=j+l)<=n)
nonprime(j); /*used to set corresponding entry(arr[j>>1]) to false*/
}
j=0;
arr[j]=2;
for(i=3;i<=n;i+=2)
{
/*if entry corresponding to i is true,i is prime and hence stored in arr[]*/
if(isprime(i))
{
arr[++j]=i;
}
}
}
int main()
{
/*call the function to store prime numbers in arr[]*/
sieve();
long int t;
/*scan the number of test cases*/
scanf("%ld",&t);
/*for each test case,access the kth entry from arr[] and print it*/
while(t--)
{
long long int k;
scanf("%lld",&k);
printf("%lld\n",arr[k-1]);
}
return 0;
}
```

## Explanation

Since we need to find **kth prime** , a simple solution is to store the 5000000(max value of k is 5000000) prime numbers so that we can answer each query in **O(1)** time. This can be done using prime sieve method.Please read this post about prime sieve before reading this post.

However,we need to perform some optimisations on basic prime sieve.

- Since all even numbers are non prime (except 2),so we need to mark odd numbers only. For example,entry corresponding to 7 will be stored at arr[7/2]=arr[3].This can also be written as
`arr[7>>1]`

. - All divide by 2 and multiply by 2 operations can be performed as bitwise operations(right shift and left shift by 1 respectively) because bitwise operations are faster.

This content has been helpful to you?

Thanks for contributing!

Pingback: SPOJ: CPRIME - Prime Number Theorem - Tuts Heap()

Pingback: SPOJ: TDPRIMES - Printing some primes - Tuts Heap()