Finding the Kth Prime | Editorial by stubborn

Finding the Kth Prime | Editorial by stubborn_toddler

Finding kth prime number - (https://www.spoj.com/problems/TDKPRIME/)
Find all prime numbers upto 100000000 using **optimized sieve method**.
1. Make a vector, for storing prime numbers and push 2  in it(since 2 is the smallest prime number)
2. Make a boolean vector for all the numbers in the range and mark initially all of them as 1.
3. Now iterate over all the odd numbers which are marked as 1 and mark all their multiples as 0.
4. Finally iterate over the boolean vector , all those which are marked as 1 are the prime numbers. Push them into the prime vector. 
```
void sieve(vector<ll> &primes)
{
    vector<bool> mark(lim+2,1);
    primes.emplace_back(2);   //emplace_back is faster than v.push_back
    for(ll i=3;i<=lim;i+=2)           //Iterating just over the odd numbers since, no even numbers other than 2 can be prime 
    {
        if(mark[i])
        {
             primes.emplace_back(i);
            for(ll j=i*i;j<=lim;j+=2*i) 
                mark[j]=0;       
        }
    }
}
```
Time Complexity - O(N log log N)

Finding the Kth Prime | Editorial by stubborn_toddler

Download submission

All caught up!

View submission

Is your resume even shortlisted?