Java – find the nth prime

I wrote the following code to find the nth prime Can this improve time complexity?

Description:

ArrayList arr stores calculated primes Once the ARR reaches the 'n' size, the loop exits and we retrieve the nth element in the ArrayList The numbers 2 and 3 are added before calculating the prime, and each number starting from 4 is checked as prime or not prime

public void calcPrime(int inp) {
    ArrayList<Integer> arr = new ArrayList<Integer>(); // stores prime numbers 
                                                      // calculated so far
    // add prime numbers 2 and 3 to prime array 'arr'
    arr.add(2); 
    arr.add(3);

    // check if number is prime starting from 4
    int counter = 4;
     // check if arr's size has reached inp which is 'n',if so terminate while loop
    while(arr.size() <= inp) {
        // dont check for prime if number is divisible by 2
        if(counter % 2 != 0) {
            // check if current number 'counter' is perfectly divisible from 
           // counter/2 to 3
            int temp = counter/2;
            while(temp >=3) {
                if(counter % temp == 0)
                    break;
                temp --;
            }
            if(temp <= 3) {
                arr.add(counter);
            }
        }
        counter++;
    }

    System.out.println("finish" +arr.get(inp));
    }
}

Solution

Yes

Your algorithm performs o (n ^ 2) operation (I may not be accurate, but it seems so), where n is the result

have http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes The algorithm adopts o (IPN * log (log (n))) You can only perform InP steps in it and assume n = 2ipn * ln (IPN) N should be larger than IPN prime We know the distribution of prime numbers http://en.wikipedia.org/wiki/Prime_number_theorem )

In any case, you can improve your existing solution:

public void calcPrime(int inp) {
    ArrayList<Integer> arr = new ArrayList<Integer>();
    arr.add(2);
    arr.add(3);

    int counter = 4;

    while(arr.size() < inp) {
        if(counter % 2 != 0 && counter%3 != 0) {
            int temp = 4;
            while(temP*temp <= counter) {
                if(counter % temp == 0)
                    break;
                temp ++;
            }
            if(temP*temp > counter) {
                arr.add(counter);
            }
        }
        counter++;
    }

    System.out.println("finish" +arr.get(inp-1));
    }
}