Shuboy
BAN USER
Questions (1)
Comments (4)
Reputation 20
- 0of 0 votes
AnswersHow to find kth prime number with k<=500000 and time limit - 1s?
- Shuboy in United States| Report Duplicate | Flag | PURGE
Algorithm
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
#include<bits/stdc++.h>
#define elif else if
#include<assert.h>
using namespace std;
#define limit 100000001
vector<bool>isprime(limit,true);
unsigned int a[5761455];
void sieve()
{
isprime[0]=isprime[1]=false;
int s=sqrt((double)limit);
for(unsigned int i=2;i<=s;i++)
{
if(isprime[i])
for(unsigned int j=i;i*j<=limit;j++)
isprime[i*j]=false;
}
int cnt=1;
a[0]=2;
for(int i=3;i<=limit;i+=2)
if(isprime[i])
a[cnt++]=i;
}
int main()
{
//std::ios::sync_with_stdio(false);
int t;
cin >> t;
sieve();
while(t--)
{
int n;
cin >> n;
cout << a[n-1] << endl;
}
return 0;
}
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
O(max-min+1)...!!
- Shuboy October 27, 2015