10001st prime

Find the nth prime number using sieve of erathoneses

Example 1:

Input : n=10
Output: 29

Approach: sieve of erathoneses

Java

import java.util.ArrayList;

import java.util.List;

public class PrimeNth1 {

    public static void main(String[] args) {

        int num = 10001, n = 10;

        int nthPrime = nthPrime(num, n);

        System.out.println("All prime " + nthPrime);

    }

    // sieve of erathoneses

    private static int nthPrime(int num, int n) {

        int prime[] = new int[1000001];

        // find which number is prime

        for (int i = 2; i * i <= 1000000; i++) {

            if (prime[i] == 0) {

                for (int j = i * i; j <= 1000000; j += i)

                    prime[j] = 1;

            }

        }

        // store all prime numbers till 1000000

        List<Integer> primes = new ArrayList<Integer>();

        ;

        for (int i = 2; i <= 1000000; i++) {

            if (prime[i] == 0)

                primes.add(i);

        }

        return primes.get(n - 1);

    }

}

// Time Complexity: O(nloglogn)

C++

#include <bits/stdc++.h>

using namespace std;

int main()

{

     //to store the prime number

    bool prime[1000001];

    memset(prime,true,sizeof(prime));

    prime[0]=false;

    prime[1]=false;

    //find which number is prime

    for(int i=2;i*i<=1000000;i++)

      {

         if(prime[i])

           {

               for(int j=i*i;j<=1000000;j+=i)

                  prime[j]=false;

           }

      }

      //store all prime numbers till 1000000

    vector<int> primes;

    for(int i=2;i<=1000000;i++)

      {

          if(prime[i])

            primes.push_back(i);

      }

   

      int n=10;

      cout<<primes[n-1]<<"\n";

    return 0;

}