0

Hello every one

Can I have a better algorithm to find the nth prime number, where 1<= n <=5000000.

for e.g.,

1st prime number is 2.

10th prime number is 29.

100th prime number is 541.

1000th prime number is 7919.

10000th prime number is 104729.

100000th prime number is 1299709.

1000000th prime number is 15485863.

Here is my code:--

```
#include<stdio.h>
#include<math.h>
long long arr[100000000]={0};
long long arr1[100000000];
int main() {
long long i,j,num,inc=2,m=0,root,q,k;
start=clock();
num=86028130;
root=sqrt(num)+1;
for(i=0;i<num;i++)arr[i]=i;
for(i=2;i<=root;i++){
if(arr[i]>0) {
for(j=inc*i;j<=num;j=j+i)
arr[j]=-1;
inc++;
}
}
for(i=0;i<num;i++) if(arr[i]>1) arr1[m++]=i;
printf("Enter value of q-");
scanf("%lld",&q);
while(q--){
printf("enter the nth prime number to be found:--");
scanf("%lld",&k);
printf("%lld\n",arr1[k-1]);
}
return 0;
}
```

range for q is <= 50000 and k inclusive 1 and 5000000.

time limit for this problem must be 10s.

but time limit for my program is exceeding for q=10.

help me with more efficient algo or techniques.