SPOJ: TDKPRIME – Finding the Kth Prime

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.

  1. 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].
  2. 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!

Yes No