[algogeeks] Finding the Kth Prime

[Wladimir Tavares]

Does anyone have any tips for this problem?

My code is time limit exceeded
#define MAX 86028122
bitset <MAX> primo;
long long int lista[5000001];
long long int cont;

void crivo(){

    long long int i,j;
    long long int limite;
    for(i=2;i<MAX;i++) primo.set(i,1);
    for(i=4;i<MAX;i=i+2) primo.set(i,0);
    lista[0]=2;
    cont=1;
    limite = sqrt(MAX);
    for(i=3;i<=limite;i=i+2){
        if(primo.test(i)){
            lista[cont++]=i;
            for(j=i*i;j<MAX;j=j+i) primo.set(j,0) ;
        }
    }

    for(i=limite+1;i<MAX;i++)
        if(primo[i]==1) lista[cont++]=i;

}

Wladimir Araujo Tavares
*Federal University of Ceará

*

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <bitset>
#define REP(i,n) for(i=0;i<n;i++)
#define MAX 86028122
using namespace std;

bitset <MAX> primo;
//char primo[MAX];
long long int lista[5000001];
long long int cont;

void crivo(){
	
	long long int i,j;
	long long int limite;
	for(i=2;i<MAX;i++) primo.set(i,1);
	for(i=4;i<MAX;i=i+2) primo.set(i,0);
	lista[0]=2;
	cont=1;
	limite = sqrt(MAX);
	for(i=3;i<=limite;i=i+2){
		if(primo.test(i)){
			lista[cont++]=i;
			for(j=i*i;j<MAX;j=j+i) primo.set(j,0) ;
		}
	}
	
	for(i=limite+1;i<MAX;i++)
		if(primo[i]==1) lista[cont++]=i;
	
}


int main(){
	
	int q,x;

	crivo();
	
	cin >> q;
	while(q--){
		cin >> x;
		cout << lista[x-1] << endl; 
	}
	
	
  return 0;
}