CareerCup

you can do it using Sieve of Eratosthenes algorithm which runs in O(nlogn)

It's kind of a misleading question though, because you cant really do it in 1 second without an initial cost of computing the tables for lookup.

One of the easiest yet efficient methods to generate a list of prime numbers if the Sieve of Eratosthenes.

Here’s the basic idea:

>Create a list with all positive integers (starting from 2 as 1 is not considered prime).
>Start at the first valid number (at this point all are valid) and eliminate all its multiples from the list. So start with 2, and eliminate 4, 6, 8, 10, 12 and so on.
>Once all the multiples are eliminated advance to the next valid number (one that has not been eliminated) and repeat the process, until there are no more valid numbers to advance to.

Sieve of Eratosthenese algo

public class PrimeSieve {
    public static void main(String[] args) {
        final int N = 500000;

        // initially assume all integers are prime
        boolean[] isPrime = new boolean[N + 1];
        for (int i = 2; i <= N; i++) {
            isPrime[i] = true;
        }

        // mark non-primes <= N using Sieve of Eratosthenes
        for (int i = 2; i*i <= N; i++) {

            // if i is prime, then mark multiples of i as nonprime
            // suffices to consider mutiples i, i+1, ..., N/i
            if (isPrime[i]) {
                for (int j = i; i*j <= N; j++) {
                    isPrime[i*j] = false;
                }
            }
        }

        // count primes
        int kPrime = Integer.parseInt(args[0]);
	// for N=500000 we can only have 41538 primes
        if ( kPrime <= 0 || kPrime > 41538 ) {
                System.out.println("Invalid Input.Please try again!!!");
                return ;
        }
        int i = 2;
        for (int primes = 0; primes < kPrime; i++) {
            if (isPrime[i]) primes++;
        }
        System.out.println("The " + kPrime + "th number of prime = " + (i-1) );
    }
}

Output:
$ java PrimeSieve 234
The 234th number of prime = 1481

$ java PrimeSieve 0
Invalid Input.Please try again!!!

vector <int> v; v.push_back(2);
for(int i=3; i<3162; i+=2)
{
if(prime[i]==false)
for(int j=i*i; j<10000000; j+=2*i)
{
prime[j] = true;
}
}

for(int i=3; i<10000000; i+=2) if(prime[i] == false) v.push_back(i);

answer is v[k]. Because v.size() is greater than 500000.

Time limit 1ms.

vector <int> v; v.push_back(2);
for(int i=3; i<3162; i+=2)
{
if(prime[i]==false)
for(int j=i*i; j<10000000; j+=2*i)
{
prime[j] = true;
}
}

for(int i=3; i<10000000; i+=2) if(prime[i] == false) v.push_back(i);

answer is v[k]. Because v.size() is greater than 500000.

Time limit 1ms.

vector <int> v; v.push_back(2);
for(int i=3; i<3162; i+=2)
{
if(prime[i]==false)
for(int j=i*i; j<10000000; j+=2*i)
{
prime[j] = true;
}
}

for(int i=3; i<10000000; i+=2) if(prime[i] == false) v.push_back(i);

answer is v[k]. Because v.size() is greater than 500000.

Time limit 1ms.

static int arr[500000]={0};
	arr[1]=1;
    for (i = 2; i < 500000; i++)
    {
        for (j = i * i; j < 500000; j+=i)
        {
            arr[j] = 1;
        }
    }

I hope this helps, algorithm used is sieve of Eratosthenes; use just have to apply your particular condition now